Solve Proof by Induction with 2 variables

1.5k Views Asked by At

I am not sure how to solve a proof by induction using $2$ variables. Do I solve for $n$ first and then $q$, or vice versa? Can you please give me a hint? Thanks.

Prove by induction on $n$ that for any real number $q>1$ and integer $n\ge 0$: $$1+q+q^2+\cdots+q^{n-1}+q^n=\frac{q^{n+1}-1}{q-1}\;.$$

1

There are 1 best solutions below

0
On BEST ANSWER

In order to prove by induction on $n$, the "standard procedure" is to prove for a base case, assume for $n = k$ for some $k \in \Bbb N$ and then to show that the argument also holds for $n = k+1$.

Base Case: Since we are given that $n \geq 0$, our lowest possible value for $n$ is $0$, so let $n=0$. Then,

$$1 = \frac{q-1}{q-1}$$

which is true, so the statement is true for $n = 0$. Your confusion here is that if $n=0$, the summation is simply

$$\sum_{k=0}^0 q^k = q^0 = 1.$$

Induction hypothesis:

Since we have shown that the statement holds for at least one $n\geq0$, let's assume that it holds for some $k\in \Bbb N$. Then

$$1 + q + q^2 + \cdots + q^{k-1} + q^k = \frac{q^{k+1} - 1}{q -1}.$$

Proof for $n = k+1$:

Now let's show that the statement holds for $n = k+1;$

If we let $n = k+1$ then we have that

\begin{align} 1 + q + q^2 + \cdots + q^k + q^{k+1} &= \frac{q^{(k+1) +1} -1}{q-1}\\ &=\frac{q^{k+2} -1}{q-1}. \end{align}

Notice that, up until the $q^{k+1}$ term, we actually have what we had in our inductive hypothesis. So we can write

$$\frac{q^{k+1} - 1}{q -1} + q^{k+1} = \frac{q^{k+2} -1}{q-1}.$$

Placing the LHS over a common denominator, we have that

\begin{align} \frac{q^{k+1} - 1 + q^{k+1}(q-1)}{q -1} &= \frac{q^{k+1} - 1 + q^{k+2}-q^{k+1}}{q -1}\\ &=\frac{q^{k+2} -1}{q-1}, \end{align}

as desired.