0
$\begingroup$

I'm having trouble starting this problem using proof by mathematical induction. I seem to know how to solve it, but the problem lies with how the summation should be set up. My professor's hint was finding a summation formula for nines(n), but that's what I keep getting confused on. Could anyone lead me into the right direction on finding the summation formula, if you even need one? I've checked some guides online and some of them don't even include summation, just the equation, however I want to take his hint into account and try to solve it that way.

The problem in question:

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 = $10^n$]. 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.

$\endgroup$
  • $\begingroup$ What is the base case ? $P(1) := [\text{nines}(1)+1=9+1=10=10^1]$. $\endgroup$ – Mauro ALLEGRANZA Mar 27 '17 at 20:36
  • $\begingroup$ Yes, I know that, but I was told to find a summation formula for nines, then use it to find the base case and inductive case. $\endgroup$ – evpmqr Mar 27 '17 at 20:38
  • $\begingroup$ Maybe this: $$\mathrm{nines}(n) = \sum_{k=1}^{n} \left(9 \cdot 10^{k-1}\right)$$ $\endgroup$ – Alexis Olson Mar 27 '17 at 20:38
  • 1
    $\begingroup$ $\text{nines}(n+1)=\text{nines}(n)*10+9$. Thus $\text{nines}(n+1) +1=\text{nines}(n)*10+9+1=(\text{nines}(n)+1)*10=10^n*10=10^{n+1}$. $\endgroup$ – Mauro ALLEGRANZA Mar 27 '17 at 20:41
  • $\begingroup$ The summation is correct: if $n=1$, then $9*10^0=9$. $\endgroup$ – Mauro ALLEGRANZA Mar 27 '17 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.