# Prove by induction $3+3 \cdot 5+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$

My question is:

Prove by induction that $$3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \frac{3(5^{n+1} -1)}{4}$$ whenever $n$ is a nonnegative integer.

I'm stuck at the basis step.

If I started with $1$. I get the right hand side is $18$ which is clearly not even close. It says prove shouldn't it be always true?

• The initial term is $3 \cdot 5^0$. – N. F. Taussig Jun 24 '16 at 13:51
• Please read this tutorial on how to typeset mathematics on this site. – N. F. Taussig Jun 24 '16 at 13:57
• What's not even close? The RHS is also 18 when $n = 1$. And as others have mentioned, the base case should be $n=0$. – tilper Jun 24 '16 at 14:12
• I actually thought it was a decimal integer but now it all adds up – RADMRA Jun 24 '16 at 15:13

For $n=1$, since $3 + 3 \times 5^1= 3+15 = 18$, there is no problem with the righthand side being $18$ too.

Note though that the base case is $n=0$, the condition being $n$ nonnegative, and then the lefthand side is $3$ as is the righthand side, which is $3 \times (5^{0+1}-1)/4 = 3$.

As you want to prove for $n$ nonnegative and integer, your basis is $n=0$

You just have to prove that $\frac{3(5^{0+1} -1)}{4} = 3$ and it is true, because $\frac{3(5^{0+1} -1)}{4} = \frac{3(5 -1)}{4} = \frac{3.4}{4} = 3$

If you want to dofor $n = 1$:

For $n=1$, you have that:

$3 + 3.5 = 18$ and $\frac{3(5^{1+1} -1)}{4} = \frac{3(5^2 -1)}{4} = 18$

• No, for n "non-negative and integer", the basis is n= 0 which reduces to 3= 3. – user247327 Jun 24 '16 at 14:05

Proof by induction on $n$;

Set your base induction for $n = 1$; which gives you $18 = 18.$

Suppose your equation is true for $n$. We are interested to prove its correctness for $n+1.$ So

$3 + 3 \times 5 + \cdots + 3 \times 5^n + 3 \times 5^{n+1} = \frac{3 \times 5^{n+1} - 3}{4} + 3 \times 5^{n+1} = \frac{3 \times 5^{n+1} - 3 + 12 \times 5^{n+1} }{4} = \frac{3 ( 5^{n+1} + 4 \times 5^{n+1}) - 3}{4} = \frac{3 ( 5^{n+2} - 1)}{4}$

by using the induction steps. And we are done!

If $\,P(n)\,$ is $\,\sum_{k=0}^{n} f(k)\, =\, g(n)$ then an inductive proof that $\,P(n)\,$ is true for all for all $\,n\ge \color{#c00}a$ has base case $\,n = \color{#c00}{a},\,$ i.e. the least value claimed true - the starting point of the induction.

Your claim is for all nonnegative integers, i.e. for all $\,n\ge \color{#c00}0,\,$ so your base case is $\,n = \color{#c00}0$.

So $\,P(0)\,$ is $\,\sum_{k=0}^{0} f(k)\, =\, g(0)$, which is simply $f(0) = g(0),\,$ true in your case by

$$f(k) = 3\cdot 5^k\, \Rightarrow\ f(\color{#c00}0) = 3\cdot 5^{\color{#c00}0} = 3 = \frac{3(5^{\color{#c00}0+1}\! -1)}{4} = g(\color{#c00}0)\,\Leftarrow\, g(n) = \frac{3(5^{n+1}\! -1)}{4}$$

The inductive step is perhaps easiest by telescopy, i.e. it simplifies as follows

If $\qquad f(0) + f(1)+\cdots + f(n)\quad =\quad \color{#0a0}{g(n)}$

then $\ \ \ f(0) + f(1)+\cdots +f(n) + \color{#90f}{f(n\!+\!1)}\,=\,\color{#0a0}{g(n\!+\!1)}\iff \color{#90f}{f(n\!+\!1)}=\color{#0a0}{g(n\!+\!1)-g(n)}$

This plus the base case $\,f(0)=g(0)\,$ combine to give an inductive proof of this Theorem:

$$\sum_{k=0}^{n} f(k)\, =\, g(n)\,\iff\, \underbrace{f(n\!+\!1) = g(n\!+\!1)-g(n)}_{\large \rm inductive\ step}\,\ {\rm and}\,\ \underbrace{f(0) = g(0)}_{\large\rm base\ case}$$

You case is $\,g(n) = \frac{3(5^{n+1} -1)}{4}\,$ so, by the above, the induction step holds true for this $\,g(n)\,$ iff $\, g(n\!+\!1)-g(n) = f(n\!+\!1) = 3\cdot 5^{n+1},\,$ which may be verified by high-school arithmetic.

Remark  Note that the theorem reduces the inductive proof to simply verifying the underbraced equations for $\,f\,$ and $\,g,\,$ which is a mechanical calculation so simple that it can be performed by a high-schoool student (or a computer). In particular, no ingenuity ("magic") is required, no rabbits need be pulled from a hat to construct the inductive step.

The inductive proof of the general theorem is much easier than that for special cases because the cancellation that occurs is much more obvious at this level of generality, whereas it is usually obfuscated by details of specific instances. Namely, the proof of the general theorem is just a rigorous inductive proof of the following telescopic cancellation

$$\underbrace{\overbrace{g(0)}^{\Large f(0)}\phantom{-g(0)}}_{\Large =\ 0}\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{-\,g(0) +\!\phantom{g(1)}}^{\Large\!\!\!\!\! +\ \ \ f(1)} \!\!\!\!\!\!\!\!\!\! \underbrace{g(1) -g(1)}_{\Large =\ 0}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\phantom{-g(1)}\!+ g(2)}^{\Large \!\!\!\!\!\!\!\!\!\!\! +\quad\ \ \ f(2) }\!\!\!\!\!\!\!\!\!\!\underbrace{\phantom{g(2)}-g(2)}_{\Large =\ 0}\!+\: \overbrace{\underbrace{\cdots\phantom{I_{I_I}\!\!\!\!\!\!\!\!}}_{\Large =\ 0}+\,\color{#0a0}{g(n)}}^{\Large \!\!\!\!\! +\ \ \ f(n)}\ =\ \color{#0a0}{g(n)}$$

You can find many more examples of telescopy and related results in other answers here. See also this answer for a more detailed proof of the Theorem.

• In your linked answer, you claim that $\displaystyle\quad\sum_{i=1}^n f(i) = g(n)\iff \color{#c00}{g(1) = f(1)}\,\ {\rm and}\,\ \color{#0a0}{g(n\!+\!1)-g(n) = f(n\!+\!1)}\$ for $\,n \ge 1$ which I understand. However you then say "Indeed, our induction proved the direction $(\Leftarrow),\,$ and $(\Rightarrow)$ is clear." We have shown that the inductive step is equivalent to the simpler equation, but why do you say we've only proved it in one direction? Also, in the formal proof I don't see any telescopy. I'd appreciate it if you would elaborate further, I want to master this. – Maxis Jaisi Jul 26 '16 at 0:33
• In the above answer, do you also mean that $f(0)-f(0)+f(1)-f(1)+...+f(n)=f(n)$ instead of $g(0)-g(0)+g(1)-g(1)+...+g(n)=g(n)$, since it's $\quad\sum_{i=0}^n f(i) = g(n)$? – Maxis Jaisi Jul 26 '16 at 0:38
• @Maxis The over/underbraced terms aim to show the cancellations that occur in such telescoping sums. This sum of the $\,f(i)\,$ is on top, Replacing the $\,f(i)\,$ via $\,f(i\!+\!1) = g(i\!+\!1)-g(i)\,$ we get the sum underneath, where successive terms cancel, collapsing like the tubes of a telescope. – Bill Dubuque Jul 26 '16 at 0:44
• @Maxis Indeed, that sentence was redundant (probably excerpted from an earlier answer with unidirectional proof). I have deleted it. Thanks for pointing it out. – Bill Dubuque Jul 26 '16 at 1:16
• @MaxisJaisi By hypothesis $\,f(n\!+\!1) = g(n\!+\!1)-g(n)\,$ is true for all $\,n,\,$ therefore for $\,n = i-1\,$ we obtain $\,f(i) = g(i)-g(i\!-\!1).\,$ That is the replacement done under the top brackets. – Bill Dubuque Jul 26 '16 at 2:20

Helping out with the problem.

I'm stuck at the basis step.

$p(n)$: $3+3 \cdot 5+ 3 \cdot 5^2+ \cdots +3 \cdot 5^n = \dfrac{3(5^{n+1} -1)}{4}$. Where $n \in \{0, 1, 2, \dots \}$.

We can rewrite the predicate. $p(n)$: $\sum_0^n3\cdot5^n = \dfrac{3(5^{n+1} -1)}{4}$

Base case: Here you need to start at 0 because we only "induct" upwards. $p(0): \sum_0^03\cdot5^n = \dfrac{3(5^{n+1} -1)}{4}$

$\implies 3 = \dfrac{3(5^1 -1)}{4} = 3 \checkmark$

Now it's up to you to show that $p(n) \implies p(n+1)$ and interpret the results.

Let $S(n)$ be the statement: $3+3\cdot{5}+\cdots+3\cdot{5^{n}}=\dfrac{3\hspace{1 mm}(5^{n+1}-1)}{4}$; $n\geq{0}$

Basis step: $S(0)$:

LHS: $3\cdot{5^{(0)}}=3$

RHS: $\dfrac{3\hspace{1 mm}(5^{(0)+1}-1)}{4}=\dfrac{3\hspace{1 mm}(5^{1}-1)}{4}$

$\hspace{35.5 mm}=\dfrac{3(4)}{4}$

$\hspace{35.5 mm}=3$

$\hspace{52.5 mm}$LHS $=$ RHS $\hspace{1 mm}$ (verified.)

Inductive step:

Assume $S(k)$ is true, i.e. assume that $3+3\cdot{5}+\cdots+3\cdot{5^{k}}=\dfrac{3\hspace{1 mm}(5^{k+1}-1)}{4}$; $k\geq{0}$

$S(k+1)$: $\underline{3+3\cdot{5}+\cdots+3\cdot{5^{k}}}+3\cdot{5^{k+1}}$

$\hspace{12.5 mm}=\dfrac{3\hspace{1 mm}(5^{k+1}-1)}{4}+3\cdot{5^{k+1}}$

$\hspace{12.5 mm}=\dfrac{3\hspace{1 mm}(5^{k+1}-1)+12\cdot{5^{k+1}}}{4}$

$\hspace{12.5 mm}=\dfrac{3\cdot{5^{k+1}}-3+12\cdot{5^{k+1}}}{4}$

$\hspace{12.5 mm}=\dfrac{15\cdot{5^{k+1}}-3}{4}$

$\hspace{12.5 mm}=\dfrac{3\cdot{5\cdot{5^{k+1}}}-3}{4}$

$\hspace{12.5 mm}=\dfrac{3\cdot{5^{k+2}}-3}{4}$

$\hspace{12.5 mm}=\dfrac{3\hspace{1 mm}(5^{k+2}-1)}{4}$

So, $S(k+1)$ is true whenever $S(k)$ is true.

Therefore, $3+3\cdot{5}+\cdots+3\cdot{5^{n}}=\dfrac{3\hspace{1 mm}(5^{n+1}-1)}{4}$; $n\geq{0}$.