Mathematical Induction?

Prove by mathematical induction that (10^n - 1) is divisible by 9 for all positive integers n.

7 Answers

Relevance
  • 1 decade ago
    Best Answer

    Base case: n=0, (10^n - 1) = 0 which is divisible by 9.

    Inductive Hypothesis: assume 9 | (10^k - 1)

    Inductive step: (10^(k+1) - 1) = (9 + 1)10^k - 1 =

    9*10^k + (10^k - 1)

    Clearly the first term is divisible by 9, and by our inductive hypothesis, the second term is divisible by 9, so (10^(k+1) - 1) is divisible by 9.

    Thus (10^n - 1) is divisible by 9 for all positive integers n.

  • Anonymous
    1 decade ago

    Assume that it's divisible for some positive integer k. Now see if it's divisible by some positive integer k+1. This would be:

    10^(k+1) - 1 =

    (10^k)(10^1) - 1 =

    (10^k)(10) - 1 =

    (10^k)(9+1) - 1 =

    9(10^k) + ((10^k) - 1)

    We know the first term is a multiple of 9. So this whole expression is divisible by 9 if (10^k - 1) is divisibile by 9 too. This shows that if (10^n - 1) is divisible by 9 for n = k, then it must be divisible by 9 for n=k+1.

    We know it works for n=1 (10^1 -1 = 9), therefore it must work 2, which means it must work for 3 also, which means it must work for 4, and so on.

  • Puggy
    Lv 7
    1 decade ago

    Prove (10^n - 1) is divisible by 9 for all n >= 1 by induction.

    Base case: Let n = 1. Then 10^n - 1 = 10^1 - 1 = 10 - 1 = 9, which is obviously divisible by 9, so the formula holds true for n = 1.

    Induction hypothesis: Assume the formula holds true for n = k; that is, assume

    (10^k - 1) is divisible by 9.

    {We want to prove that 10^(k + 1) - 1 is divisible by 9}

    But what does 10^(k + 1) - 1 equal?

    10^(k + 1) - 1 =

    10*10^k - 1

    Separate 10*10^k into 9*10^k + 1*10^k, we obtain

    9*10^k + 1*10^k - 1

    But the 1 is redundant, so we have

    9*10^k + 10^k - 1

    I'll put brackets around each term to prove a point.

    (9*10^k) + (10^k - 1)

    Now, (10^k - 1) is divisible by 9 because of our induction hypothesis.

    (9*10^k) is OBVIOUSLY divisible by 9.

    The sum of two numbers divisible by 9 is itself divisible by 9. This means

    10^(k + 1) is divisible by 9,

    and hence, by the principle of mathematical induction,

    (10^n - 1) is divisible by 9 for all n >= 1.

  • 1 decade ago

    for n = 1, it holds true, because (10^1 - 1) is divisible by 9 9/9 = 1.

    assume it holds true for all k, so (10^k - 1) = 9m where m is some integer. this is from the definition of divisble.

    now, prove it holds true for k + 1, so you will have this:

    (10^(k+1) - 1) = 9j where j is some integer.

    (10^k * 10^1 -1) = 9j

    since you know that 10^k - 1 is divisible by 9, you can say 9m * 10^1. knowing that mulitplication between integers is still an integer 9m*10^1 can be rewritten as 9h, where h is an integer.

    Source(s): note, this is a guide, it's been a while since i've done proof by induction. but this should be a good guide.
  • How do you think about the answers? You can sign in to vote the answer.
  • 1 decade ago

    It is true for n=1 10-1=9

    Suppose it true for n=h

    so 10^h-1 is a multiple of 9 (a)

    We must prove that 10^(h+1)-1 is a multiple of nine

    10(h+1)-1 =10^h*10-1 But by (a) 10^h = k*9 +1

    so 10^h*10 -1= 10k*9 +10 -1 = (10k+1)*9 .So we proved that it is divisible by 9

  • 1 decade ago

    RTP 10^n - 1=9

    Proof:

    1) First prove true for n=1

    10^1 - 1=9 (which is true)

    2)Assume true for n=k

    10^k -1=9A

    3)Show true for n=k+1

    10^(k+1) - 1 = 9B

    10^k * 10 = 9B +1

    (9A +1)10 = 9B +1 {by assumption made above}

    9A(10) +9 - 9B

    9(10A-B+1) {which is always divisible by 9 }

    Source(s): Einstein is my uncle
  • 3 years ago

    you like 2 issues: a base case and an "inductive bounce of religion". then you definately instruct the two. in this actual occasion, your base case would be S(a million), and your "bounce of religion" would be that whether that's genuine for S(n), then it is likewise genuine for S(n+a million). S(a million) = a million^2 = a million * 2 * 3 / 6 = a million. Sp. genuine for S(n), instruct for S(n + a million). purpose: instruct that S(n+a million) = (n + a million)(n + 2)(2n + 3) / 6 = (n^2 + 3n + 2)(2n + 3) / 6 = (2n^3 + 9n^2 + 13n + 6) / 6 initiate with the definition of S(n+a million): S(n+a million) = S(n) + (n+a million)^2 = S(n) + n^2 + 2n + a million and then replace the equation for S(n), utilising the inductive hypothesis: S(n+a million) = n(n + a million)(2n + a million) / 6 + n^2 + 2n + a million = (2n^3 + 3n^2 + n) / 6 + n^2 + 2n + a million = ((2n^3 + 3n^2 + n) + (6n^2 + 12n + 6)) / 6 = (2n^3 + 9n^2 + 13n + 6) / 6 by utilising the way, you may desire to ascertain you know this evidence, and then attempt to prepare it to a minimum of something else.

Still have questions? Get your answers by asking now.