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.

  • 1
    $\begingroup$ Not very readable without MathJax. Do you mean $U_{n+2}-3U_{n+1}+2U_n=0$ ? $\endgroup$ – MPW Jun 12 '18 at 22:55
  • $\begingroup$ 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. $\endgroup$ – Suzet Jun 12 '18 at 22:56
  • $\begingroup$ 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"$$ $\endgroup$ – 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$:








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

  • $\begingroup$ Thanks a lot...i'm writting a National exam tommorow and never taught of the double assumption stuff...'saved m $\endgroup$ – 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$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.