3
$\begingroup$

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!!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you @mrtaurho! I'm glad my attempt was going in the right direction! But is there a formal reason for why the basis case is n = 0? Although, it is a fair step, considering n = 0 does work perfectly when looking at the statement. $\endgroup$ – Rikk Nov 28 '18 at 21:40
  • $\begingroup$ @Rikk I general you try to find the smallest possible natural number for which it works out. In your case it is given that $n\in\mathbb N$ - or at least you assumed that it has to be so - and $n=0$ is the first possible value of this set. In case it does not works out for $0$, one may consider $n=1$ and so on. Take a look at this for an example where you cannot start by setting $n=0$. $\endgroup$ – mrtaurho Nov 28 '18 at 21:43
  • $\begingroup$ Fair! I am so used to using n = 1, that I have forgotten about using 0 as the first possible value of natural numbers. Thank you a lot for your clarification, regardless! $\endgroup$ – Rikk Nov 28 '18 at 21:46
  • $\begingroup$ No problem. I am happy that I could clear your doubts :) $\endgroup$ – mrtaurho Nov 28 '18 at 21:47
0
$\begingroup$

Well ...

Write down that assertion when $n=1$ and verify that it's true.

Assume that it's true for some particular (unspecified) value of $n$. Write down what that tells you - I recommend doing that with an ellipsis $$ 1 + q + q^2 + \cdots + q^n = \ldots $$ Then add $q^{n+1}$ and see if you can turn that into what you want.

Having said that, I wish you didn't have to use induction. It's much easier just expanding with the distributive law: $$ (q-1)(1 + q + q^2 + \cdots + q^n) . $$ Induction should be saved for problems where it really helps.

$\endgroup$
0
$\begingroup$

Hint:

The set in which the arithmetic operations take place has no importance. You indeed have use induction on the exponent.

The simplest, from my point of vizw, would be to prove by induction the factorisation formula: $$x^{n}-1=(x-1)(x^{n-1}+x^{n-2}+\dots+x+1).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.