0

We have the predicate $P(n) = 10^0 + 10^1 + 10^2 + ... + 10^n < 10^{n+1}$, $n >= 0 $

To prove by induction we need to check the base case $P(0)$, and after that we have our induction hypotheses where we assume that the predicate is true for some $k = n$. After that we need to show that if $P(k)-->P(k+1)$ then it's true for all $n>=0$.

Base case: $P(0) = 10^0 = 1 < 10^1 = 10$ TRUE

Induction hypothesis: $10^0 + 10^1 + 10^2 + ... + 10^k < 10^{k+1}$, for some $k = n$.

Induction step $P(k+1)$: try to prove this

$10^0 + 10^1 + 10^2 + ... + 10^k + 10^{k+1} < 10^{n+2}$

...

That's where I'm lost. How can I show that $10^0 + 10^1 + 10^2 + ... + 10^k + 10^{k+1}$ is less than it's successor?

... I think I solved it. Thank you abiessu.

$10^0 + 10^1 + 10^2 + ... + 10^k + 10^{k+1} < 10^{k+1} + 10^{k+1}$

Know I need to show that $10^{k+1} + 10^{k+1}$ < $10^{k+2}$

$10^{k+1} + 10^{k+1} = 2*10^{k+1}$

$10^{k+2} = 10*10^{k+2}$

So we show that $2*10^{k+1} < 10*10^{k+2}$

$10^0 + 10^1 + 10^2 + ... + 10^k + 10^{k+1} < 10^{k+1} + 10^{k+1} = 2*10^{k+1} < 10^{k+2} = 10*10^{k+2}$

Therefore we can conclude our proof by mathematical induction that $10^0 + 10^1 + 10^2 + ... + 10^k + 10^{k+1} < 10^{k+2} = 10*10^{k+2}$

Will
  • 19

1 Answers1

5

Your hypothesis is that $$10^0 + 10^1 + 10^2 + ... + 10^k < 10^{k+1}$$ Therefore $$10^0 + 10^1 + 10^2 + ... + 10^k + 10^{k+1} < 10^{k+1} + 10^{k+1}$$

Can you continue from there?

F.Carette
  • 1,346
  • Why did you modify $10^{k+2}$ by $10^{k+1} + 10^{k+1}$ ? $10^{k+2}$ is not equal to $10^{k+1} + 10^{k+1}$, I do not get it, can you explain it? – Will Dec 14 '22 at 14:48
  • @Will: what is another way to write $10^{k+2}$ in terms of $10^{k+1}$? Or, can you use $2\lt 10$? – abiessu Dec 14 '22 at 14:50
  • @Will I didn't replace $10^{k+2}$, I just took the Induction hypothesis and add $10^{k+1}$ on both side of the inequality. From there, and using abiessu comment, you have to make the $10^{k+2}$ appear – F.Carette Dec 14 '22 at 14:55
  • @abissu but $10^{k+2} = 10^{k+1}.10^1$? How did you manipulate $10^{k+2}$ to become $10^{k+1} + 10^{k+1}$ ? – Will Dec 14 '22 at 14:56
  • @Will He did not modify $10^{k+2}$ in that way. All he has done to get from the first equation to the second equation is add $\ 10^{k+1}$ to both sides. – Adam Rubinson Dec 14 '22 at 15:07
  • @abiessu Can you check my answer to see if it's correct? I edited my post – Will Dec 14 '22 at 15:09