# Strong Induction Problem using Summations

• May 3rd 2009, 09:09 AM
tshare1
Strong Induction Problem using Summations
Let an be the recurrence defined by $a_{0} = 1$ (for all n > 0)
$a_{n} = 1 + \sum_{i=0}^{n-1}a_{i}$

Prove using strong induction that (for all n greater than or equal to 0) $a_{n} = 2^{n}$

Any help is appreciated!
• May 3rd 2009, 09:10 AM
TheEmptySet
Quote:

Originally Posted by tshare1
Let an be the recurrence defined by a0 = 1 (for all n > 0)
$a_{n} = 1 + \sum_{i=0}^{n-1}$

Prove using strong induction that (for all n greater than or equal to 0) $a_{n} = 2^{n}$

Any help is appreciated!