# Proof by Mathematical Induction for a sequence of integers.

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.

• – TheSilverDoe Oct 27 '20 at 14:02

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

$$u_{n+1}=3(2^n+1)-2(2^{n-1}+1)=3\times2^n+3-2^n-2=2\times2^n+1=2^{n+1}+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

$$u_{k+1}=3u_{k}-2u_{k-1}=3\cdot2^{k}+3-2\cdot2^{k-1}-2=3\cdot2^k-2^k+1$$

$$=2\cdot2^k+1=2^{k+1}+1$$.