Prove By Induction $U_n=2^n+1.$

Question

Given that $U_1=3,U_2=5,$ and $U_{n+2}-3U_{n+1}+2U_n=0.$

Show that $U_n=2^n+1.$

I'm stuck at showing that if $P(n+1)$ is true if $P(n)$ is true.

Answer 1

Consider that it is true for $n=1$ and $n=2$:

$n=1\implies U_n=2^1+1=3$

$n=2\implies U_n=2^2+1=5$.

Now, assume that it is true for $n=k$ and $n=k+1$. We prove that it is true for $n=k+2$.

Substitute $n=k$ (this is different from the previous $n$) into the equation $U_{n+2}-3U_{n+1}+2U_n=0$:

$$U_{k+2}-3U_{k+1}+2U_k=0$$

$$U_{k+2}=3U_{k+1}-2U_k$$

$$U_{k+2}=3(2^{k+1}+1)-2(2^{k}+1)$$

$$U_{k+2}=3\times2^{k+1}+3-2\times2^{k}-2$$

$$U_{k+2}=3\times2^{k+1}-\times2^{k+1}+1$$

$$U_{k+2}=2\times2^{k+1}+1$$

$$U_{k+2}=\times2^{k+2}+1$$

Therefore, the equation is true for $n=k+2$.

Because the equation is true for $n=1$ and $n=2$, and it being true for $m=k$ and $n=k+1$ makes it true for $n=k+2$, it is true for all positive integers $n$.

It's like an infinite line of dominoes, but it takes $2$ dominoes to make the next fall. Because the first $2$ dominoes ($n=1$ and $n=2$) fall (fulfils the equation), then all the dominoes fall (equation is true for all positive integers $n$).

Answer 2

It's hard using induction. The characteristic equation is $$z^2-3z+2=0$$which has two roots $$z_1=1\\z_2=2$$then the equation of $U_n$ is $$U_n=a\cdot2^n+b\cdot1^n$$which by substituting $U_1$ and $U_2$ yields the same result.

alternative way (induction)

Consider $w_n=u_{n+1}-u_{n}$ therefore$$w_{n+1}=2w_n$$with $w_1=2$ which leads to $$w_n=2^n$$also $$u_{n+1}=u_n+2^n$$ or $$u_{n+1}=u_1+2+2^2+2^3+2^4+\dots +2^n=2+1+2+2^2+2^3+2^4+\dots +2^n=2^{n+1}-1+2=2^{n+1}+1$$or alternatively$$u_n=2^n+1$$