Problem
ALG-B1-M10-P019 Linear recurrence
#19
★★★★☆ Level 4 of 5
Let \(u_0=1\), \(u_1=3\), \(u_{n+2}=3u_{n+1}-2u_n\). Prove that \(u_n=2^{n+1}-1\).
Check the base cases and make the induction step.
For \(n=0,1\), the formula is true. If \(u_n=2^{n+1}-1\) and \(u_{n+1}=2^{n+2}-1\), then \(u_{n+2}=3(2^{n+2}-1)-2(2^{n+1}-1)=2^{n+3}-1\). The formula is proved.
A recurrence among other types tests recognition.