Maybe solve using linear algebra: Set A = [[4,3],[2,3]]. Then: (x_n, y_n)^T = A*(x_{n-1}, y_{n-1})^T And thus (x_n, y_n)^T = A^n * (x_0, y_0)^T = A^n * (7, 7)^T Now calculate A^n using diagonalization
Just find the eigenvalues of A, and find the corresponding eigenvectors. As long as the starting condition is linearly independent from the nondominant eigenvectors (e.g. not proportional to the one nondominant eigenvector), then the eigenvector corresponding to the larger eigenvalue will be proportional to the limit. det(sI-A)=(s-4)(s-3)-3*2=s^2-7s+6 = (s-6)(s-1) -> s=6 or s=1 s=6 will dominate. Consider eigenvector for s=6, or v=[x,1]'. Av = 6v by definition. We can take either row of this equation. Bottom is perhaps easier: [2,3]*[x,1]' = 2x+3 = 6, or x=3/2. Now check the eigenvector for s=1: 2x+3 = 1 or x=-1. The initial condition of [7,7]' cannot be expressed in terms of the [-1,1]' eigenvector alone and thus must have a [3/2,1]' component. The latter will dominate as n goes to infinity. Thus x/y will go to 3/2. To be slightly more formal, [7,7]' = a*[3/2,1]'+b*[-1,1]'. We could work out what a and b are, but it only matters that a is nonzero. Then A^n*[7,7]' = a*6^n*[3/2,1]' + b*1^n*[-1,1]. As n goes to infinity, the first term dominates.
My method is to let t_n=x_n/y_n=(4t_n-1+3)/(2t_n-1+3). Assume t_n converge to L. We can convert it to L=(4L+3)/(2L+3). Solve the equation, and then we can get L=3/2.
The last two recurrence relations - xn - x(n - 1) = 7 * 6^n and yn - y(n - 1) = 14/3 * 6^n - can be solved through standard methods quite easily. To obtain a particular solution, one can easily guess xn = (6 * 7)/5 * 6^n. Then the characteristic polynomial simply says that all of the solutions are of the form x(p) + C, so checking for the inital condition gives xn = (6 * 7)/5 * 6^n - 7/5 which is the solution that was obtained in the video. A similar thing works for yn.
i think you can just use formula 1 divide by formula 2, Xn/Yn=(4Xn-1/Yn-1+3)/(3+2Xn-1/Yn-1). limit both side, assume the limit Xn/Yn=k, then limit Xn-1/Yn-1 = k too. then you have k=(4k+3)/(3+2k) then k = -1 or 3/2. k must be positive so k = 3/2
Nice soln. Just an observation: you could find a recurrence for x_n+y_n with the constant 6 because (1, 1) is a left eigenvector of the corresponding matrix, with eigenvalue 6. With this in mind, one could also calculate the left eigenvector (2,-3) corresponding to the eigenvalue 1 and derive the recurrence 2x_n-3y_n= 2x_(n-1) -3y_(n-1) and solve for x_n, y_n using these two. Or, you could divide these two recurrences to get a recurrence for x_n/y_n
I see a lot of methods in the comments, but not one like mine, so here it is: Using the Stolz-Cesaro theorem we immediately get that the limit they ask for is equal to 3A/2A = 3/2, where A= x_{n-1}+y_{n-1} Edit: I just saw Siddharda’s comment
My method: From the first equation, y_n = (x_{n+1} - 4x_n)/3 Substitute into the second equation and simplifying: x_{n+1} - 7x_n + 6x_{n-1} = 0 Since x^2 - 7x + 6=0 has roots 6 and 1, so x_n = A * 6^n + B * 1^n = A * 6^n + B, where A and B are constants. Using x_0 = 7 and compute x_1 = 49, x_n = (42 * 6^n-7)/5 Substitute back into y_n = (x_{n+1} - 4x_n)/3, y_n = (28 * 6^n + 7)/5 Take limit to get 3/2
As n tends to infinity Xn/Yn=Xn-1/Yn-1 =k. say Now Xn/Yn = (4Xn-1+3Yn-1)/(3Yn-1/2Xn-1) Dividing by Yn-1 in numerator and denominator of RHS and putting the expression for k, we get a quadratic equation in k. Solve to get k=3/1
After some operation: Xn=4Xn-1+6Xn-2+9Yn-2 Xn=4Xn-1+6Xn-2+3Xn-1-12Xn-2 Xn=7Xn-1-6Xn-2. Then r^2-7r+6=0, with roots 1 and 6. Then Xn=C1*1^n + C2*6^n. From X0 and X1 we get C1=-7/5 and C2=6*7/5 and Xn=7/5 * (6*6^n-1) Same way Yn=7/5 * (4*6^n+1). After that is very easy to se that the limit is 6/4=3/2. The liniar recurention are 3 years highschool level, so, this method is ok. More of that, if the roots of characteristics equation are complex, then the form of Xn and Yn contain cos and sin, which cannot be observed so easy from other method.
this question reminds me of a recurrence relation i stumbled across a while ago, and was quite amazed to find (using sympy) that a certain expression factorized. given x_0 and y_0 the relation is: x_n+1 = A *x_n + M * B * y_n y_n+1= N*B * x_n + A * y_n Where rather remarkably : M * (y_n)^2 - N*(x_n)^2 = (A^2 - M*N*B^2)^n * (M*(y_0)^2 - N* (x_0)^2)
I tried to do this with linear algebra: (x_n // y_n) = (4 3 // 3 2) (x_{n-1} // y_{n-1}) but got bogged down a little in getting the explicit formulas for x_n, y_n - I could probably have stopped when I got to a basic surd solution, and taken the limit directly.I really like your "trick" solution, though!
Here is an even simpler trick. Let t = lim(x_n/y_n). Notice that t = lim(x_n-1/y_n-1). Divide Equation1 by Equation 2 and take limit on both sides, one gets: t = (4t +3)/(3 + 2t). Solve it, t = -1 or 3/2. Since lim(x_n/y_n)>0, so lim(x_n/y_n) = 3/2.
Is it possible to simply guess 3/2 by the first values of x_n and y_n, then show that it is a "fixpoint" (if x_n/y_n = 3/2 also x_n+1 / y_n+1 = 3/2) and take it from there? It shouldn't be too hard, to show, that x_n/y_n is strictly increasing when it is between 1 and 3/2 and that it also
I converted this into a matrix system, found the eigenvalues/eigenvectors, wrote down the general solution, implemented the initial values, wrote down the ratio of the two specific solutions, and took the limit as n tends to infinity; took me much less time than your video... only 5 minutes.
In the same way that simultaneous linear ODEs in x and y can be cracked using eigenvalues and eigenvectors, I suspect an analogous approach would work here.
It is one liner by stolz cesaro theorem
Orzz
Nice!
Maybe solve using linear algebra:
Set A = [[4,3],[2,3]]. Then:
(x_n, y_n)^T = A*(x_{n-1}, y_{n-1})^T
And thus
(x_n, y_n)^T = A^n * (x_0, y_0)^T
= A^n * (7, 7)^T
Now calculate A^n using diagonalization
Yep, most systematic way to solve this. This is how I did it.
Just find the eigenvalues of A, and find the corresponding eigenvectors. As long as the starting condition is linearly independent from the nondominant eigenvectors (e.g. not proportional to the one nondominant eigenvector), then the eigenvector corresponding to the larger eigenvalue will be proportional to the limit.
det(sI-A)=(s-4)(s-3)-3*2=s^2-7s+6 = (s-6)(s-1) -> s=6 or s=1
s=6 will dominate.
Consider eigenvector for s=6, or v=[x,1]'. Av = 6v by definition. We can take either row of this equation. Bottom is perhaps easier: [2,3]*[x,1]' = 2x+3 = 6, or x=3/2.
Now check the eigenvector for s=1: 2x+3 = 1 or x=-1.
The initial condition of [7,7]' cannot be expressed in terms of the [-1,1]' eigenvector alone and thus must have a [3/2,1]' component. The latter will dominate as n goes to infinity. Thus x/y will go to 3/2.
To be slightly more formal, [7,7]' = a*[3/2,1]'+b*[-1,1]'. We could work out what a and b are, but it only matters that a is nonzero. Then A^n*[7,7]' = a*6^n*[3/2,1]' + b*1^n*[-1,1]. As n goes to infinity, the first term dominates.
My method is to let t_n=x_n/y_n=(4t_n-1+3)/(2t_n-1+3). Assume t_n converge to L. We can convert it to L=(4L+3)/(2L+3). Solve the equation, and then we can get L=3/2.
You have to prove that t_n surely converges.
@@田村博志-z8y Yes i just use monotonic convergence theorem to prove it.
This method works generely
@@aashsyed1277 Yeah. This is just a basic method in linear algebra.
The last two recurrence relations - xn - x(n - 1) = 7 * 6^n and yn - y(n - 1) = 14/3 * 6^n - can be solved through standard methods quite easily. To obtain a particular solution, one can easily guess xn = (6 * 7)/5 * 6^n. Then the characteristic polynomial simply says that all of the solutions are of the form x(p) + C, so checking for the inital condition gives xn = (6 * 7)/5 * 6^n - 7/5 which is the solution that was obtained in the video.
A similar thing works for yn.
Excellent explanation sir
Could you have reduced your steps by using delta x/ delta y = 7/14/3 = 3/2
i think you can just use formula 1 divide by formula 2, Xn/Yn=(4Xn-1/Yn-1+3)/(3+2Xn-1/Yn-1). limit both side, assume the limit Xn/Yn=k, then limit Xn-1/Yn-1 = k too. then you have k=(4k+3)/(3+2k)
then k = -1 or 3/2. k must be positive so k = 3/2
Before setting the limiting value, you have to prove that the sequence converges.
@@田村博志-z8y right, need to prove xn/yn has a upper boundary. not that hard though since both formula are linear.
Nice soln. Just an observation: you could find a recurrence for x_n+y_n with the constant 6 because (1, 1) is a left eigenvector of the corresponding matrix, with eigenvalue 6. With this in mind, one could also calculate the left eigenvector (2,-3) corresponding to the eigenvalue 1 and derive the recurrence 2x_n-3y_n= 2x_(n-1) -3y_(n-1) and solve for x_n, y_n using these two. Or, you could divide these two recurrences to get a recurrence for x_n/y_n
I see a lot of methods in the comments, but not one like mine, so here it is:
Using the Stolz-Cesaro theorem we immediately get that the limit they ask for is equal to 3A/2A = 3/2, where A= x_{n-1}+y_{n-1}
Edit: I just saw Siddharda’s comment
well...this was screaming for a Z-transform ...
Please speak loud.
My method:
From the first equation, y_n = (x_{n+1} - 4x_n)/3
Substitute into the second equation and simplifying:
x_{n+1} - 7x_n + 6x_{n-1} = 0
Since x^2 - 7x + 6=0 has roots 6 and 1, so x_n = A * 6^n + B * 1^n = A * 6^n + B, where A and B are constants.
Using x_0 = 7 and compute x_1 = 49, x_n = (42 * 6^n-7)/5
Substitute back into y_n = (x_{n+1} - 4x_n)/3, y_n = (28 * 6^n + 7)/5
Take limit to get 3/2
As n tends to infinity Xn/Yn=Xn-1/Yn-1
=k. say
Now Xn/Yn =
(4Xn-1+3Yn-1)/(3Yn-1/2Xn-1)
Dividing by Yn-1 in numerator and denominator of RHS and putting
the expression for k, we get a quadratic equation in k. Solve to get k=3/1
Very good problem enjoyed it👍👍
After some operation:
Xn=4Xn-1+6Xn-2+9Yn-2
Xn=4Xn-1+6Xn-2+3Xn-1-12Xn-2
Xn=7Xn-1-6Xn-2.
Then r^2-7r+6=0, with roots 1 and 6. Then Xn=C1*1^n + C2*6^n. From X0 and X1 we get C1=-7/5 and C2=6*7/5 and Xn=7/5 * (6*6^n-1)
Same way Yn=7/5 * (4*6^n+1). After that is very easy to se that the limit is 6/4=3/2.
The liniar recurention are 3 years highschool level, so, this method is ok. More of that, if the roots of characteristics equation are complex, then the form of Xn and Yn contain cos and sin, which cannot be observed so easy from other method.
Nice with multiple roots
this question reminds me of a recurrence relation i stumbled across a while ago, and was quite amazed to find (using sympy) that a certain expression factorized. given x_0 and y_0 the relation is:
x_n+1 = A *x_n + M * B * y_n
y_n+1= N*B * x_n + A * y_n
Where rather remarkably :
M * (y_n)^2 - N*(x_n)^2 = (A^2 - M*N*B^2)^n * (M*(y_0)^2 - N* (x_0)^2)
I think we can use generating formal power series in order to transform this recession into simple system of linear differential equations.
I tried to do this with linear algebra: (x_n // y_n) = (4 3 // 3 2) (x_{n-1} // y_{n-1}) but got bogged down a little in getting the explicit formulas for x_n, y_n - I could probably have stopped when I got to a basic surd solution, and taken the limit directly.I really like your "trick" solution, though!
Very beautiful soln :))
Here is an even simpler trick. Let t = lim(x_n/y_n). Notice that t = lim(x_n-1/y_n-1). Divide Equation1 by Equation 2 and take limit on both sides, one gets: t = (4t +3)/(3 + 2t). Solve it, t = -1 or 3/2. Since lim(x_n/y_n)>0, so lim(x_n/y_n) = 3/2.
Is it possible to simply guess 3/2 by the first values of x_n and y_n, then show that it is a "fixpoint" (if x_n/y_n = 3/2 also x_n+1 / y_n+1 = 3/2) and take it from there? It shouldn't be too hard, to show, that x_n/y_n is strictly increasing when it is between 1 and 3/2 and that it also
nice one
3/2 I mean.
I converted this into a matrix system, found the eigenvalues/eigenvectors, wrote down the general solution, implemented the initial values, wrote down the ratio of the two specific solutions, and took the limit as n tends to infinity; took me much less time than your video... only 5 minutes.
I’d love to see how to do this ❤️
@@zackjames2409 just like you would do a linear system of differential equations, tbh.
In the same way that simultaneous linear ODEs in x and y can be cracked using eigenvalues and eigenvectors, I suspect an analogous approach would work here.