(Note you do not need to have seen the original olympiad problem to answer my question)
I was attempting the fifth problem from the 2008 Canadian Mathematical Olympiad, and got all the way to this line in the proof ($r$ is a sequence of numbers, $r_1=1$ and $r_2=4$):
$$ r_{n+1} + 1 = 2(r_{n}+1)+ (r_{n-1}+1)$$
The next line of the provided solution then goes to this:
$$ r_{n} + 1 = {1\over 2\sqrt{2}}(1+\sqrt{2})^{n+1} – {1\over 2\sqrt{2}}(1-\sqrt{2})^{n+1}$$
While I see how this line could be proved via induction, I do not understand how they have got from the first line to the second in the first place; can anyone provide an 'intuitive' way to get to the iterative version of a recursive function, and perhaps how to do so more generally as well? Ideally answers would not use concepts much beyond high school math since after all this is a high school olympiad.
All answers are much appreciated.
Best Answer
Let $u_n = r_n+1$ like the other solution, which is motivated by the fact that no $r_i$ is not without a +1.
Our relation is $$u_{n+1} = 2u_n + u_{n-1}.$$
Our goal is to find an expression that gives us the closed form. In general, we can create the characteristic polynomial of a relation $d_n = ad_{n-1} + bd_{n-1}$ as $x^2 -ax - b = 0.$ When the roots of this are $r_1,r_2,$ the closed form is $d_n = \alpha r_1^n + \beta r_2^n,$ where alpha and beta are constants. This pretty well known, but the intuition is that we expect $d_n,$ a second degree recurrence relation, to grow close to exponentially.
Anyways, we use this to find $r_1$ and $r_2$ (quadratic formula suffices).
Now, we can solve for the constants $\alpha$ and $\beta.$
This is the general method to finding the closed form of nasty second degree recurrence relations, I'm not sure if that helps you much. The main idea is the close to exponential growth of relations like these, to put it shortly.