a finite induction question from burton's elementary number theory

Question

this question comes from burton's elementary number theory, 4th edition.

question 3 in 1.1 says to use the second principle of finite induction to establish that

$$for\ all\ n\ge1,\ ^{(a)}\ a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a+1)$$

$[hint;\ ^{(b)}\ a^{n+1}-1=(a+1)(a^n-1)-a(a^{n-1}-1).]$

my question comes from the solution manual, where in the first step of induction, where they demonstrate the proposition is true for $n=1$, $^{(a)}$ becomes $a-1=a-1$, and so it must be shown that the proposition stands after $n=k$.
now when $n=1$, clearly $a^n-1=a-1\iff\ n=1$.
further, $(a-1)(a^{n-1}+a^{n-2}+...+a+1)=(a-1)$ identically when $(a^{n-1}+a^{n-2}+...+a+1)=1$

so to show that $(a^{n-1}+a^{n-2}+...+a+1+1)=1$

this is my work so far;

$$a^{n-1}+a^{n-2}+...+a+1=\sum_{i=1}^{\inf}a^{n-i}=a^n\sum^{\inf}_{i=1}a^{-i},\ when\ n=1\ \Rightarrow\ a^n\sum_{i=1}^{\inf}a^{-i}=a\sum^{\inf}_{i=1}a^{-i}$$

which requires that $$^{(c)}\ \sum_{i=1}^{\inf}a^{-i}=a^{-1}$$

so $$a\sum_{i=1}^{\inf}a^{-i}=a(a^{-1})=1$$

verifying the 1st step in induction...

and that is my question, proving $^{(c)}$

Answer 1

I feel that you need to do a bit of work on thoroughly understanding induction. To prove $$a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a+1)\tag{$*$}$$ for $n\ge1$ you need to do two things:

• prove that if $n=1$ then $(*)$ is true;
• prove that if $(*)$ is true for $1,2,\ldots,n$, then it is true for $n+1$.

The first step is easy, as long as you look carefully at what the second factor means when $n=1$. In this case the first term is $a^0=1$ and the last term is $1$. These are actually the same term, so the "in between terms" are not really there, the first and last are just one term, and the factor is just $1$. So in this case, $(*)$ reads $$a^1-1=(a-1)(1)$$ which is clearly true.

Now assume that $(*)$ is true for $1,2,\ldots,n$, and use the hint you were given: $$a^{n+1}-1=(a+1)(a^n-1)-a(a^{n-1}-1)\ .$$ Since we have assumed that $(*)$ is true for $n$ and $n-1$, we have $$\eqalign{ a^n-1&=(a-1)(a^{n-1}+a^{n-2}+...+a+1)\cr a^{n-1}-1&=(a-1)(a^{n-2}+a^{n-3}+...+a+1)\ ;\cr}$$ substituting these into the "hint" equation gives $$\eqalign{a^{n+1}-1&=(a+1)(a-1)(a^{n-1}+a^{n-2}+...+a+1)\cr &\qquad\qquad\qquad{}-a(a-1)(a^{n-2}+a^{n-3}+...+a+1)\cr &=\cdots\cr &=(a-1)(a^n+a^{n-1}+\cdots+a+1)\cr}$$ and so $(*)$ is true for $n+1$. By induction, $(*)$ is true for all $n\ge1$.

See if you can finish this by supplying the small amount of algebra I have omitted.