Let $u_0,u_1,u_2,...$ be a sequence of integers given by $u_0=2, u_1=3$ and $u_{n+1}=3u_n-2u_{n-1}$ for every integer $n\ge1$. Then $u_n=2^n+1$ for all $n\in \Bbb N_0$.

I let $P(n)$ be $u_{n+1}$ and then let $P(1)=u_{1+1}=3u_1-2u_0=5$ after substituting in the corresponding values. I'm confused as to what my next step should be as I'm not sure what $u_{1+1}=5$ proves.


(Just adding some more detail about how induction works. Basically J.W. Tanner's explanation fleshed out a bit more).

Don't have $P(n)=u_{n+1}$ or something like that. Have $P(n)$ be a statement. In this case:

$P(n)$ is the statement "$u_{n}=2^n+1$"

Base Case

$P(0)$ is true since $u_0=2=2^0+1$

$P(1)$ is true since $u_1=3=2^1+1$

Induction Step

Now, using (strong) induction: assume $P(0), ..., P(n)$ and we will prove $P(n+1)$.

$u_{n+1}=3u_n-2u_{n-1}$ by definition. Let's subsitute in the values for $u_n$ and $u_{n-1}$


Which verifies that $u_{n+1}=2^{n+1}+1$ which verifies $P(n+1)$.


$u_0=2=2^0+1$ and $u_1=3=2^1+1$.

Now assume $u_{k-1}=2^{k-1}+1$ and $u_{k}=2^{k}+1$. Then




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.