0
$\begingroup$

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}$

$\endgroup$
5
  • 1
    $\begingroup$ By the inductive hypothesis it is less than $10^{k+1}+10^{k+1}$ $\endgroup$
    – Henry
    Dec 14, 2022 at 14:44
  • $\begingroup$ If $a\lt b$ with both integer, then $10a +1\lt 10b$ $\endgroup$
    – abiessu
    Dec 14, 2022 at 14:44
  • 1
    $\begingroup$ Pick one of the two generic approaches described in this answer. $\endgroup$ Dec 14, 2022 at 14:48
  • 1
    $\begingroup$ Just a slight remark : An easier proof is $11\cdots 11<100 \cdots 00$ where on the left side we have $n+1$ ones and on the right side $n+1$ zeros. $\endgroup$
    – Peter
    Dec 14, 2022 at 14:48
  • $\begingroup$ Your idea is correct, but you kept using $k+2$ in a couple places where you should use $k+1$. $\endgroup$
    – abiessu
    Dec 14, 2022 at 16:54

1 Answer 1

5
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Will
    Dec 14, 2022 at 14:48
  • $\begingroup$ @Will: what is another way to write $10^{k+2}$ in terms of $10^{k+1}$? Or, can you use $2\lt 10$? $\endgroup$
    – abiessu
    Dec 14, 2022 at 14:50
  • $\begingroup$ @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 $\endgroup$
    – F.Carette
    Dec 14, 2022 at 14:55
  • $\begingroup$ @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}$ ? $\endgroup$
    – Will
    Dec 14, 2022 at 14:56
  • $\begingroup$ @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. $\endgroup$ Dec 14, 2022 at 15:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .