Double induction example: $ 1 + q + q^2 + q^3 + \cdots + q^{n-1} + q^n = \frac {q^{n+1}-1}{q-1} $
I'm working on a double induction problem with the following prompt:
Prove by induction on $n$ that for any real number $q > 1$ and integer $n \ge 0$: $$ 1 + q + q^2 + q^3 + \cdots + q^{n-1} + q^n = \frac {q^{n+1}-1}{q-1} $$
Based on Induction on two integer variables, I would imagine the solution is:
- Base case $(q,n)$ as $(2,n)$ and $(q,0)$
- Assume premise for $(2,n)$ and prove $n+1$
- Assume premise for $(q,0)$ and prove $q+1$
But even the base cases confuse me...for example on $(q,0)$: $$1+q^0 = \frac {q^{0+1}-1}{q-1} $$ $$2 = 1 $$
That can't right. Maybe I omit the $q^0$ on the LHS, but why?
The problem says "for any real number $q>1$..." You can't do (standard) mathematical induction on the real numbers (see here though).
As the problem itself explicitly states, you are supposed to do induction on $n$. There is no "double induction" here. The number $q$ should be treated as just a given real number.
There is no double induction, as there is only one variable running through the natural numbers.
You can just leave $q$ as an indeterminate; note that the expression is $$ q^0+q^1+\dots+q^n $$ and this means that, for $n=0$, it is just $q^0=1$. So the base step is true.
For the inductive step, $$ q^0+q^1+\dots+q^n+q^{n+1}=\frac{q^{n+1}-1}{q-1}+q^{n+1}= \frac{q^{n+1}-1+q^{n+2}-q^{n+1}}{q-1} $$ and you're done.
The only restriction on $q$ is $q\ne1$ (somebody would say also for $q=0$, but if we consider $0^0=1$ the relation still holds).
$$\dfrac{q^{n+1}-1}{q-1}+q^{n+1}=\dfrac{q^{n+1}-1}{q-1}+\dfrac{q^{n+2}-q^{n-1}}{q-1}=\dfrac{q^{n+2}-1}{q-1}$$ and $$q^0=1=\dfrac{q^{0+1}-1}{q-1}$$ That's a proof by induction I think.