So I had to solve the following problem...
Xn+1 - 5Xn + 4Xn-1 = 0 X1 = 9 and X2 = 33
So I set X = 1 and got:
X1+1 - 5X1 + 4X1-1 = 0
(33) - 5(9) + 4X0 = 0
33-45 + 4X0 = 0
-12 + 4X0 = 0
4X0 = 12
X0 = 3
So we know that X0= 3, X1=9, and X2=33
Knowing this, how do I write the equation?? The equation is Xn = 1 + 2 * 4n However, I have no idea how to arrive at that equation if the book did not tell me. Any help please? There are many problems like these, I can always solve for X but I can't find the general equation.
You can virtually "see" this one
if you already know the powers of 2: 3 is 1 greater than 2, 9 is 1 greater than 8, and 33 is one greater than 32, and 2, 8, and 32 are the successive odd powers of 2.
So \(\displaystyle x_n = 1 + 2^{(2n - 1)} = 1 + 2 * 2^{2n} = 1 + 2 * 4^n. \)
But perhaps you do not "see" that the powers of 2 are involved. What next?
If successive terms differ by a constant factor, you can discover the common factor as follows: \(\displaystyle x_{n + 1} = a * x^n \ne 0 \implies \dfrac{x_{n + 1}}{x_n} = a.\)
That does not work here because 9 / 3 = 3 and 33 / 9 > 3.
If successive terms differ by a constant, you can find the constant as follows: \(\displaystyle x_{n + 1} = x_n + a \implies a = x_{n + 1} - x_n.\)
That does not work here because 9 - 3 = 6 and 33 - 9 = 24. But maybe there is a ratio between these differences. 24 / 6 = 4.
We need more examples to see if there is a pattern.
\(\displaystyle x_3 - 5x_2 + 4x_1 = 0 \implies x_3 - 5 * 33 + 4 * 9 = 0 \implies x_3 = 165 - 36 = 129.\)
\(\displaystyle x_4 - 5x_3 + 4x_2 = 0 \implies x_3 - 5 * 129 + 4 * 33 = 0 \implies x_4 = 645 - 132 = 513.\)
So now the successive differences are 6, 24, 129 - 33 = 96, and 513 - 129 = 384.
But what are the ratios of the successive differences 24 / 6 = 4, 96 / 24 = 4, 384 / 96 = 4.
OK, it looks as though 4 is involved as follows:
\(\displaystyle \dfrac{x_{n + 1} - x_n}{x_n - x_{n - 1}} = 4 \implies x_{n + 1} - x_n = 4x_n - 4x_{n - 1} \implies x_{n + 1} - 5x_n + 4x_{n - 1} = 0.\) We are definitely on the right track.
In fact, 24 / 6 = 4, 96 / 6 = 16, 384 / 6 = 64. It looks as though powers of 4 are involved.
\(\displaystyle x_1 = 9 = 2 * 4 + 1 = 1 + 2 * 4^1.\)
\(\displaystyle x_2 = 33 = 2 * 16 + 1 = 1 + 2 * 4^2.\)
\(\displaystyle x_3 = 129 = 2 * 64 + 1 = 1 + 2 * 4^3.\)
\(\displaystyle x_4 = 513 = 2 * 256 + 1 = 1 + 2 * 4^4.\)
This looks very promising. If this pattern works \(\displaystyle 1 + 2 * 4^0 = 1 + 2 * 1 = 1 + 2 = 3 = x_0.\)
Now lets test.
\(\displaystyle x_n = 1 + 2 * 4^n \implies x_{n + 1} - 5x_n + 4x_{n - 1} = 1 + 2 * 4^{(n+1)} - 5\left(1 + 2 * 4^n\right) + 4(1 + 2 * 4^{n-1)}) =\)
\(\displaystyle 1 + 2 * 4^{(n + 1)} - 5 - 10 * 4^n + 4 + 8 * 4^{(n - 1)} =\)
\(\displaystyle 2 * 4^{(n + 1)} - 10 * 4^n + 8 * 4^{(n - 1)} =\)
\(\displaystyle 2 * 4^2 * 4^{(n - 1)} - 10 * 4^1 * 4^{(n-1)} + 8 * 4^{(n - 1)} =\)
\(\displaystyle 4^{(n - 1)}(2 * 4^2 - 10 * 4^1 + 8) = 4^{(n - 1)}(2 * 16 - 10 * 4 + 8) = 4^{(n - 1)}(32 - 40 + 8) = 4^{(n - 1)} * 0 = 0.\)
I do not know a general method for finding a closed form for a recursively defined function. I generally work out a number of terms of the recursion and then start taking differences, ratios, ratios of differences until I find some consistent element and then start trying to use that consistent element as part of a pattern. If you take this experimental approach, you
must then test to make sure that the pattern is not spurious.