Proving recurrence function with sigma notation?

Question

Btw zero is a natural number in this case.

I'm confused on how to handle the sigma in the inductive step, oh and im just trying to prove $f_2(n) = 2^n$ so ignore the second half.

My attempt:

Prove $P(n): f_2(n) = 2^n, \forall n \in \mathbb N$ I'll proceed with strong induction

Base cases:

let $n = 0$

$P(0): f_2(0) = 1 = 2^0 = 2^n$ [def of $P(0)$]

Induction step: Let $n > 0$

Suppose $f_2(j) = 2^j$ whenever $0 \leq j < n$ [I.H]

WTP: $P(n): f_2(n) = 2^n$

THEN:

$P(n): f_2(n) = 1 + \sum_{i=0}^{n-1} f_2(i)$ [def of $f_2(n)$; $n > 0$]

= Sigma throws me off. Idk how I would rearrange the sigma to use my inductive hypothesis.

Answer 1

Apply the induction hypothesis to rewrite the sum as $$ f_2(n)=1+\sum_{i=0}^{n-1}2^i. $$ This is now just a geometric series. Can you go from here?