Question: Consider the following non linear recurrence relation defined for $n \in \mathbb{N}$:
$$a_1=1, \ \ \ a_{n}=na_0+(n-1)a_1+(n-2)a_2+\cdots+2a_{n-2}+a_{n-1}$$
a) Calculate $a_1,a_2,a_3,a_4.$
b) Use induction to prove for all positive integers that:
$$a_n=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{3+\sqrt{5}}{2}\right)^n-\left(\dfrac{3-\sqrt{5}}{2}\right)^n\right]$$ Hi all! I'm having trouble solving this problem. I have no problem with part (a), but I'm having lots of troubles with part (b). I proved the base case (which is quite trivial), but I'm having trouble for the inductive step (proving k->k+1).
I don't know what to do from this point. Thank you!
In fact, your recurrence relationship can be transformed into this second order relationship:
whose characteristic equation is $r^2-3r+1=0$ with roots $r_1=\tfrac{3+\sqrt{5}}{2}$ and $r_2=\tfrac{3-\sqrt{5}}{2}$, which does not come as a surprise.
Proof of (*). Let us write the definition for two consecutive elements:
$$\tag{1}\begin{cases}a_n=na_0+(n-1)a_1+\cdots+3a_{n-3}+2a_{n-2}+1a_{n-1}\\ a_{n+1}=(n+1)a_0+(n)a_1+\cdots+3a_{n-2}+2a_{n-1}+1a_n \end{cases}$$
Subtracting the first equation to the second equation, we get:
$$\tag{2}a_{n+1}-a_n=\sum_{k=0}^n a_k$$
If we write (2) at the next order:
$$\tag{3}a_{n+2}-a_{n+1}=\sum_{k=0}^{n+1} a_k$$
Subtracting (2) from (3), we get:
$$a_{n+2}-2a_{n+1}+a_n=a_{n+1}$$
which proves relationship (*).
Now, it shouldn't be difficult for you to prove by recurrence that the solution of (*) is $a_n=\tfrac{1}{\sqrt{5}}(r_1^n-r_2^n)$.