The function nines(n) returns a natural number consisting of n nines, where n is a natural number greater than or equal to 1. For example:

nines(1)	=	9
nines(2)	=	99
nines(3)	=	999
nines(4)	=	9999
	?

In questions 13, use mathematical induction to prove that the following is true for all k, where k is a natural number greater than or equal to 1.

nines(k) = 10^k ? 1

Your proof must use the induction schema (P(1) ? ?k [P(k) ? P(k + 1)]) ? ?k P(k) as described in the lectures.

1. (5 points.) Write P(1) using a summation. Prove that it is true.

2. (5 points.) Write P(k) and P(k + 1) using summations.

3. (10 points.) Using your answers from 2, prove that ?k [P(k) ? P(k + 1)] is true.

You will lose points if you do not use summations, or if your proof does not use the induction schema.