0

Prove by mathematical induction that, for $q\ne1$, and integer $r\ge 0$,
$$a+aq+\cdots+aq^r = \dfrac{a(q^{r+1}-1)}{q-1} $$

Unsure where is my $~n~$ to sub my $~k+1~$ in this case, as there are $~3~$ variables.

Will require a really simplified answer if possible, beginner discrete mathematics.

Edit: Selected Rick's answer as his was more complete, but I personally understood through Marty's method. Thank you all for taking a look at my question.

Detective merry
  • 115

3 Answers3

0

first of all I want to make sure that you get the fact that there is only one variable of induction and that is the 'r' as the 'a' and 'q' are constants that are already assigned some values. So we should proceed further by using principle of mathematical induction only on r

p(1) = sum of only one term = first term = a hence it is true ! Suppose that:- p(r-1) is true then we have to check the validity of p(r). For this you can use the fact that p(r-1) + $ a q^r$ and use some mathematical manipulation to prove it is also true.

28ADY0901
  • 706
0

You want to show that $\sum_{k=0}^r aq^k = \dfrac{a(q^{r+1}-1)}{q-1} $.

The $a$ is common to both sides, so it cancels out and you want to show that $\sum_{k=0}^r q^k = \dfrac{q^{r+1}-1}{q-1} $.

For $r=0$, this is $1 = \dfrac{q-1}{q-1} $, which is true.

If it true for $r$, then, looking at the sum for $r+1$,

$\begin{array}\\ \sum_{k=0}^{r+1} q^k &=\sum_{k=0}^{r} q^k+q^{r+1} \qquad\text{split off last term}\\ &=\dfrac{q^{r+1}-1}{q-1}+q^{r+1} \qquad\text{use the induction hypothesis}\\ &=\dfrac{q^{r+1}-1+(q-1)q^{r+1}}{q-1} \qquad\text{algebra}\\ &=\dfrac{q^{r+1}-1+q^{r+2}-q^{r+1}}{q-1} \qquad\text{ more algebra}\\ &=\dfrac{q^{r+2}-1}{q-1} \qquad\text{and we are done}\\ \end{array} $

marty cohen
  • 107,799
0

This is just the formula for geometric finite series once you take the $a$ common.

$$a(1+q+q^2+q^3+...+q^r) = \frac{a(q^{r+1}-1)}{q-1} $$

Let's try to prove this formula via induction.

Induction step 1, check for base case i.e $ r = 0$,

L.H.S. = $ a(1) = a$, R.H.S. = $ \frac{a(q^{r+1}-1)}{q-1}=\frac{a(q^{0+1}-1)}{q-1} = \frac{a(q-1)}{q-1} = a$. Hence L.H.S. = R.H.S. and base case is true.

Induction step 2, assume formula is true for $r = k \Rightarrow a(1+q+q^2+...+q^k) = \frac{a(q^{k+1}-1)}{q-1}$

We will show it holds for $ r= k+1$. When $r =k+1$, then

$a(1+q+...+q^{k+1}) = a(1+q+...+q^k)+ aq^{k+1}$

Using the fact that we assumed the formula to be true for $r =k$, we substitute the value of $a(1+q+q^2+...+q^k)$ from step 2 to obtain: $L.H.S. = a(1+q+...+q^k)+aq^{k+1} = \frac{a(q^{k+1}-1)}{q-1} +aq^{k+1} = \frac{a(q^{k+1}-1)+aq^{k+1}(q-1)}{q-1}= \frac{a(q^{k+1}-1)+aq^{k+2}-aq^{k+1}}{q-1} = \frac{aq^{k+2}-a}{q-1} = \frac{a(q^{(k+1)+1}-1)}{q-1}$

This is what was needed.

Rick
  • 1,099
  • Thank you, but I am confused at the addition of aq^(k+1) on RHS. Why is it divided by q-1 and how did the aq^(k+2) come about. Edit: So sorry, just realised its algebra – Detective merry Sep 14 '19 at 09:59
  • It is just simple manipulation. $aq^{k+2}$ come simply by taking l.c.m. and adding the terms $\frac{a(q^{k+1}-1)}{q-1}$ and $aq^{k+1}$. – Rick Sep 14 '19 at 10:03