Define two sequences an and bn by recursion let a0 1 and

Question

1. Define the following sequence by recursion: a₀ = 1 and for all integers' n > 0, a_n = 1 + _i=0Σ^n-1 2a_i.

Show by induction that for all integers n ≥ 0, a_n = 3ⁿ.

Note: you may use the geometric series formula, which we proved in class: _nΣ^k=m r^k = r^m-rⁿ⁺¹/1-r.

2. Define the following sequence by recursion: a₀ = 2, and for all integers' n > 0, a_n = 2 + 2_i=0Σ^n-1 a_i.

Show by induction that for all integers n ≥ 0, a_n ≤ 4ⁿ⁺¹.

Note: it is possible to determine an exact formula for an, but this is not the easiest way to solve the problem.

3. Define two sequences (a_n) and (b_n) by recursion. Let a₀ = 1, and let a_n =√2 · a_n-1 whenever n > 0.

Let b₀ = 5 and b₁ = 5, and let b_n = b_n-1 + b_n-2 whenever n > 1. Show that for all n ≥ 0, b_n > a_n.

Note: this is the hardest problem on the page, probably.

4. Show by strong induction that for all positive integers n, there are integers a and b where n = 3^ab and 3b.

Note: do not use the prime factorization theorem! You can (and should) use its proof to inspire your answer to this problem, though.

5. Show that the representation from (4) is unique. That is, if n = 3^ab and n = 3^cd, and a, b, c, d are all integers, and 3 b and 3 d, then a = c and b = d.

6. Show that for all integers n ≥ 43, there are nonnegative integers a and b where n = 6a+ 7b.

7. Show that for all integers n ≥ 0, if n is divisible by four, then 5|2ⁿ⁺² + 3ⁿ⁺⁴.