I just recently covered 'rational numbers' in class and was assigned the following question to solve using induction for n
, so that for all $q \in \mathbb{Q}$ \ {1}:
$$\sum_{k=0}^n q^k = \frac{q^{n+1}-1}{q-1}$$
I am not entirely sure on where to start, since up to this point I've only done proofs by induction involving natural numbers only. I've thought about leaving the variable q
as it is, and doing
n = 1
then assuming statement is true for n, solve for n + 1
where $n \in \mathbb{N}$, but it leaves me with a dead end, since there are too many unknown variables involved.
I hope someone can help me with this question and explain to me what the best approach would be and why!
Thank you!!
Answer
Your attempt is right! You do not have to change the $q$; leave it as it is and do the standard induction regarding to $n$.
Therefore lets start with our basis case $n=0$:
$$\begin{align}
\sum_{k=0}^0q^k&=\frac{q^{0+1}-1}{q-1}\\
1&=1
\end{align}$$
Next consider the new values $n=m$ and $n=m+1$ which corresponde to the two equations
$$\begin{align}
\sum_{k=0}^{m}q^k&=\frac{q^{m+1}-1}{q-1}\\
\sum_{k=0}^{m+1}q^k&=\frac{q^{m+2}-1}{q-1}
\end{align}$$
Here the first one is our assumption the second one our hypothesis. Howsoever lets split up the second sum as the following
$$\sum_{k=0}^{m+1}q^k=\underbrace{\sum_{k=0}^{m}q^k}_{=\text{assumption}}+q^{m+1}$$
As we can see the remaining sum equals our assumption. Therefore we can replace it by the given fraction from above. This yields to
$$\sum_{k=0}^{m}q^k+q^{m+1}=\frac{q^{m+1}-1}{q-1}+q^{m+1}=\frac{q^{m+1}-1+q^{m+2}-q^{m+1}}{q-1}=\frac{q^{m+2}-1}{q-1}$$
And thus we have shown that from our assumption the hypothesis follows and therefore we are done.
No comments:
Post a Comment