Prove by induction that $F(n+1) = F(n)×2$ for $n \ge 1$

50 Views Asked by At

$$F(n)=\begin{cases} 1 & \; \text{if} \; n = 0 \\ \sum_{i=0}^{n-1} F(i)& \; \text{if} \; n > 0\end{cases}$$

This gives,

$F(0) = 1$

$F(1) = F(0) = 1$

$F(2) = F(0) + F(1) = 2$

$F(3) = F(0) + F(1) + F(2) = 4$

$F(4) = F(0) + F(1) + F(2) + F(3) = 8$

and so on...

Prove by induction that $F(n+1) = F(n)×2$ for $n\ge 1$

1

There are 1 best solutions below

0
On BEST ANSWER

If you don't know how induction works, it shortly begins with proving what is required to prove for (for example) $n=1$ and then assuming it is also true up to $n-1$, now if you proved that it (what you're trying to prove) is true for $n$ then you will be done.

Here for $n=1$, $F(n+1)=F(2)=2=2\times 1=2\times F(1)$ (first step of the induction is done).

Suppose it is true up to order $n-1$ which means that $F(n)=F(n-1)\times 2$ (the second step of induction).

Now you only have to prove that $F(n+1)=F(n)\times 2$ using what we have just supposed that it is true.

So, $$F(n+1)=\sum\limits_{i=0}^{n}F(i)=F(0)++F(1)+\sum\limits_{i=2}^{n}2\times F(i-1)= \\ =F(0)+F(1)+ 2\times\sum\limits_{i=2}^{n}F(i-1)= \\ =2\times F(0)+ 2\times\sum\limits_{i=1}^{n-1}F(i)= 2\times\sum\limits_{i=0}^{n-1} F(i)=F(n)\times 2. $$