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

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.

• Not very readable without MathJax. Do you mean $U_{n+2}-3U_{n+1}+2U_n=0$ ? – MPW Jun 12 '18 at 22:55
• You need to assume that both the steps $n$ and $n+1$ are true in order to show the step $n+2$. This is a double induction. – Suzet Jun 12 '18 at 22:56
• You haven't said what $P(n)$ is, but a cute trick is to define: $$P(n):=\quad "U_{n}=2^n+1 \text{ and } U_{n+1}=2^{n+1}+1"$$ – Thomas Andrews Jun 12 '18 at 23:28

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$).

• Thanks a lot...i'm writting a National exam tommorow and never taught of the double assumption stuff...'saved m – Lee Jun 12 '18 at 23:28

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$$

• This approach, while very nice, assumes a theory, the proof of which, I suspect, depends on induction.... – Barry Cipra Jun 12 '18 at 23:06
• I included that way either..... – Mostafa Ayaz Jun 12 '18 at 23:19
• Thanks but please where is that"Characteristic Equation" from – Lee Jun 12 '18 at 23:24
• It's much easier using induction than that answer. – Thomas Andrews Jun 12 '18 at 23:27
• You're welcome......the characteristics function has been emanated from $Z-transform$ $$H(z)=\sum_{-\infty}^{\infty}h[n]z^{-n}$$ – Mostafa Ayaz Jun 12 '18 at 23:35