Prove by induction

Question

$F(n)$ for $n \geq 1$ is defined as the sum of all previous values of F

$$F(0) = 1$$

Prove by induction over n that:

$F(n) = 2^{n-1} \text{ for } n \geq 1$.

These are my steps: $$F(n) = 2^0+2^1+\dots+2^{n-1}= 2^n$$ from here on out i cant seem to find any basecases to fulfill the right side and left side. Left = Right in order to move on. could someone show me the steps to solve this type of induction, so that I can understand it for other types of induction as well.

Answer 1

Supposed $F(0)=1$ is set and for $n \in \mathbb{N}$ you define $F(n) = \sum_{i=0}^{n-1} F(i)$. You can prove it with induction:

IS: $n=1: F(1)=F(0)=1=2^0=2^{1-1}$

Suppose you have proven it for a fixed $n \in \mathbb{N}$, now try to show this also holds for $n+1$:

$$F(n+1)=\sum_{i=0}^{n} F(i) = F(n) + \sum_{i=0}^{n-1} F(i) = 2 \cdot F(n)$$

Inserting your induction hypothesis you are finished.

Answer 2

Hint (for $n>0$):$$F(n+1)=F(1)+\cdots+F(n-1)+F(n)=F(n)+F(n)=2F(n)$$

Answer 3

Given $F(n) = \sum_{k = 0}^{n - 1} F(k)$,

$$F(n) = 2^n$$ $$\sum_{k=0}^{n - 1}F(k) = 2^n $$ $$F(n) + \sum_{k=0}^{n - 1}F(k) = F(n) + 2^n $$ $$\sum_{k=0}^n F(k) = 2^n + 2^n $$ $$F(n + 1) = 2^{n + 1} $$