Induction proof question

64 Views Asked by At

Show by induction that for all integers n $\ge$ 1 $$ \sum_{i=1}^n i3^i = \frac{3(2n3^n-3^n+1)}{4} $$

Starting with n = 1 will give me LHS = 3 and RHS = 3.

Inserting n = p gives $$\sum\limits_{i=1}^p i3^i = \frac{3(2p3^p-3^p+1)}{4} $$

Going to n = p+1 gives me LHS $$\frac{3(2p3^p-3^p+1)}{4} +(p+1)3^{p+1}$$

I tried to expand the RHS for $$\frac{3(2(p+1)3^{p+1}-3^{p+1}+1)}{4}$$ so it becomes $$\frac{3(2p+2)3^{p+1}-3^{p+1}+1)}{4}$$ then $$\frac{3(p(2+2)3^{p+1}-3^{p+1}+1)}{4}$$ until $$\frac{3(p(2+2)3*3^{p}-3*3^{p}+1)}{4}$$

Is this the right way to expand this formula?

1

There are 1 best solutions below

4
On

There seem to be numerous typos, either in terms of missing parentheses, or mismatched variables in your solution.

In particular, the claim is written as $\sum\limits_{i=1}^n i3^i=\frac{3(2i3^i-3i+1)}{4}$. Surely, you mean to have $n$'s on the RHS instead of $i$'s.

The line that begins "inserting $n=p$ gives", shouldn't that be $\sum\limits_{i=1}^p i3^i = \frac{3(2p3^p-3p+1)}{4}$. Why do you write $p3^p$?

After the phrase "so it becomes" you have $\frac{3(2p+2)3^{p+1}-3^{p+1}+1)}{4}$ which has a total of one left parenthesis and two right parenthesis. Surely, you meant to say $\frac{3\color{red}{(}(2p+2)3^{p+1}-3^{p+1}+1)}{4}$

The next line which begins "then" you have $\frac{3(p(2+2)3^{p+1}-3^{p+1}+1)}{4}$. How did that step go? $(2p+2)\neq p(2+2)$ in general (only for the one case when $p=1$)

You have made a good start, but there is still more manipulation to do before you finally get the LHS to appear equal the RHS. It is usually easier to put things into a fraction than take things out of a fraction, so I would suggest continuing to work on the LHS a bit more.

For information on how to format an induction proof, I recommend viewing this answer.


For the beginnings of a better worded proof:

Claim: $\sum\limits_{i=1}^ni3^i = \frac{3(2n3^n-3n+1)}{4}$ for all $n\geq 1$

Proof: The claim holds for $n=1$.

Let us assume for our induction hypothesis that $\sum\limits_{i=1}^pi3^i = \frac{3(2p3^p-3p+1)}{4}$ for some $p\geq 1$. Then for $p+1$ we have:

$$\begin{array}{lll} \sum\limits_{i=1}^{p+1}i3^i &= (p+1)3^{p+1}+\sum\limits_{i=1}^p i3^i\\ &=(p+1)3^{p+1}+\frac{3(2p3^p-3p+1)}{4}&\text{by induction hypothesis}\\ &=\frac{4p3^{p+1}+4\cdot 3^{p+1}}{4}+\frac{3(2p3^p-3p+1)}{4}\\ &=\frac{4p3^{p+1}+4\cdot 3^{p+1} + 2p3^{p+1}-9p+3}{4}\\ &=\frac{6p3^{p+1}+4\cdot 3^{p+1} - 9p+3}{4}\\ &\vdots \end{array}$$