Induction and Recursion: $F(1) = 2$ and $F(n) = F(n - 1) + F(n - 2) + \dotsb + F(1) + 2$, $n \ge 2$

Question

We have this:

$F(1) = 2$

$F(n) = F(n - 1) + F(n - 2) + \dotsb + F(1) + 2$, $n \ge 2$

And we need:

1) give a recursive definition of $F(n)$

2) prove using mathematical induction that for every positive integer $n$, $F(n) = 2^n$.

Answer 1

Hint

$$F(n) = F(n - 1) + F(n - 2) + \dotsb + F(1) + 2$$

$$F(n+1) = F(n)+ F(n - 1) + F(n - 2) + \dotsb + F(1) + 2$$

so,

$$F(n+1)-F(n)=F(n)$$ $$F(n+1)=2F(n)$$

Is it suggest you something?