## Math 310: Problem set 3

*Instructions*: This problem set is due
Friday, January 27, 2006.
Your goal is not only
to give correct answers but to communicate
your ideas well. Make sure you use good English,
- Let f(n) be the sum of the first n natural numbers
which are triples plus 1 (i.e., the sum of the first n numbers from the sequence
4, 7, 10, ... .) Thus f(1) = 4, f(2) = 4 + 7, and f(n) = 4 + 7 + ... + (3n+1) for n >= 3.
- (a) Use induction to prove that f(n) = n(3n+5)/2 for n >= 1.
- (b) Give a second proof by deriving the
formula f(n) = n(3n+5)/2 from the formula
1 + 2 + 3 + ... + n = n(n+1)/2.

- Let a
_{1} = 3, a_{2} = 9, and, for integers n > 1,
let a_{n+1} = 2a_{n} + 3a_{n-1}.
Use a version of induction to prove for all integers n > 0, that
a_{n} = 3^{n}.