Homework 1: Induction practice

Homework 1: Induction practice

1. Use induction to prove that if an is a sequence such that a0 = 0 and
an = 2an−1 + 2n for n > 0, then an = n2
n for all n ≥ 0.
2. Use strong induction to prove that if bn is a sequence such that b0 = 1,
b1 = 6, and bn = 4bn−2, then bn = 2n+1 − (−2)n for all n ≥ 0.
Hence, an = 2n+1 − (−2)n for all n ≥ 0 by strong induction.
1