Confusion with Discrete Math Induction example

Question

I am currently working on learning proof by induction. One of the examples in my textbook is confusing me with regards to the algebraic manipulation around the induction step. Here we are trying to prove by induction that $10^0+10^1+...+10^n<10^{n+1},$ where $n$ is a natural number

The inequality is:

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

Can someone help me understand the algebraic manipulation that goes into getting this result?

Answer 1

Here, inductive hypothesis should be that we have $$10^0+10^1+10^2+...+10^k < 10^{k+1}$$ Then we are trying to verify whether $10^0+10^1+10^2+...+10^k+10^{k+1} < 10^{k+2}$ is true or not. By using inductive hypothesis, we have $$10^0+10^1+10^2+...+10^k < 10^{k+1}$$ Now, adding $10^{k+1}$ to both sides, we get $$10^0+10^1+10^2+...+10^k+10^{k+1} < 10^{k+1}+10^{k+1} = 2\cdot10^{k+1}$$ But we know that $2\cdot10^{k+1} < 10\cdot10^{k+1} = 10^{k+2}$. Therefore, by transitivity of $<$, we have $$10^0+10^1+10^2+...+10^k+10^{k+1} < 10^{k+2}$$

Answer 2

So the first line $10^0+10^1+.....$ leaves you with $10^{k+1}$, but with all of the $0$'s replaces with $1$'s. So you have $1$ concatenated $k+1$ times. This is clearly less than $2\cdot 10^{k+1}$, which is just $2$ followed by $k$ zeroes. Which is then clearly less than $10\cdot 10^{k+1}$ as this is an order of magnitude greater.

Answer 3

In this problem used the fact that $$10^0+10^1+10^2+\cdots+10^k<10^{k+1}$$ this is the inductive hipotesis. Then the next step is show that $10^0+10^1+10^2+\cdots+10^k+10^{k+1}<10^{k+2}$

Answer 4

You can use induction to prove the more general result: $\sum_{i=0}^n a^i= \frac{1- a^{n+1}}{1- a}$.

When n= 0 the sum is just $a^0= 1$ and $\frac{1- a^{0+1}}{1- a}= \frac{1- a}{1- a}= 1$.

Assume that, for some n= k, $\sum_{i=0}^k a^i= \frac{1- a^{k+1}}{1- a}$. Then $\sum_{i=0}^{k+1} a^i= \sum_{i=0}^k a^i+ a^{k+1}= \frac{1- a^{k+1}}{1- a}+ a^{k+1}$$= \frac{1- a^{k+1}}{1- a}+ \frac{a^{k+1}- a^{k+2}}{1- a}= \frac{1-a^{k+2}}{1- a}$ and we are done.

Your specific case follows by taking a= 10: $\sum_{i=0}^n 10^n= \frac{1- 10^{n+1}}{1- 10}= \frac{1}{9}(10^{n+1}- 1)$.