Mathematical induction: If n is an integer greater than or equal to 1, then the
ID: 3806160 • Letter: M
Question
Mathematical induction:
If n is an integer greater than or equal to 1, then the function nines(n) returns an integer made up of n 9’s. For example:
nines(1)
=
9
nines(2)
=
99
nines(3)
=
999
nines(4)
=
9999
Let P(n) [nines(n) + 1 = 10n]. Prove that P(n) is true for all n 1, by mathematical induction. Use the induction schema [P(1) k [P(k) P(k + 1)]] n P(n).
1. (5 points.) What is the base case, P(1)?
2. (5 points.) What is the inductive case, k [P(k) P(k + 1)]?
3. (10 points.) Use your answers from questions 1 and 2 to construct the proof.
nines(1)
=
9
nines(2)
=
99
nines(3)
=
999
nines(4)
=
9999
Explanation / Answer
1)By mathematical inducation,let n=1
nines(n)+1=10n
L.H.S:nines(1)+1=9+1=10(since,nines(1)=9)
=10(1)
R.H.S:10n=10(1)(since we took n=1)
therefore,L.H.S=R.H.S
2) Inductive case, k [P(k) P(k + 1)]:
let us assume that for a moment, P (k) is true
nines(n)+1=10n
=> nines(k)+1=10k
We'll show the truth of P(k+1) is true
L.H.S:nines(k)+1=nines(k+1)+1
R.H.S:10k=10(k+1)
3)proof: i.e.,nines(k)+1=10k=>nines(k+1)+1=10(k+1)
Thus if P (k) is true then P(k+1) is true.
therefore,k [P(k) P(k + 1)]
Hence ,proved