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

Question

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?

Answer 1

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$.

Answer 2

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$

Answer 3

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.

Answer 4

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.

Answer 5

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}$.

Answer 6

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!