Prove by induction that $13+23^2+33^3 + \cdots + n3^n = \dfrac{3}{4}(3^n(2n-1)+1)$

Question

I'm trying to prove this using induction $1*3+2*3^2+3*3^3 + \cdots + n*3^n = \dfrac{3}{4}(3^n(2n-1)+1)$

So far I have:

Base case: true
Induction step: $\dfrac{3}{4}(3^n(2n-1)+1)+(n+1)*3^{n+1}=\dfrac{3}{4}(3^{n+1}(2(n+1)-1)+1)$

here is where I get stuck on simplification of both left and right side so that they are equal $\dfrac{3}{4}(3^n(2n-1)+1)+3^{n+1}+3^{n+1}n=\dfrac{3}{4}(3^{n+1}(2(n+1)-1)+1)$

Thanks for your help!

You don't really need induction to prove this formula. – Bernard Dec 10 '20 at 20:23 — Bernard, Dec 10 '20 at 20:23

score 2 · Accepted Answer · answered Dec 10 '20 at 20:10

Notice that $$3^{n+1}(n+1) = 3 \cdot 3^n (n+1) = \frac{3}{4} \cdot 3^n \cdot 4(n+1)$$ Because of the 3/4, you can move this term into the parentheses and combine it with the $3^n(2n-1)+1$ part. And because of the $3^n$, you can move the $4(n+1)$ into the parentheses and combine with the $2n-1$ part, to get

$$ \frac{3}{4} \left( 3^n (2n-1) + 1 \right) + 3^{n+1}(n+1) = \frac{3}{4} \left( 3^n \left(6n+3 \right) + 1 \right) $$

Notice that $6n+3 = 3(2n+1)$, so in the parentheses you get $3^{n+1}(2n+1)+1$.

score 0 · Answer 2 · edited Dec 10 '20 at 20:59

In the induction step you want to prove the increment from $n$ to $n+1$ on both sides are the same, namely,

$$(n+1)3^{n+1} = \dfrac{3}{4}(3^{n+1}(2n+1)-3^n(2n-1))\tag1$$

By looking at the increment you got rid of the annoying constant $1$ from the RHS. Then you notice immediately that you can divide $3^{n+1}$ from both sides, and $(1)$ becomes

$$n+1 = \dfrac{1}{4}(3(2n+1)-(2n-1))=\frac 14 (6n+3-2n+1)=\frac 14 (4n+4)=n+1$$

then you are done.

Prove by induction that $1*3+2*3^2+3*3^3 + \cdots + n*3^n = \dfrac{3}{4}(3^n(2n-1)+1)$

2 Answers2

Prove by induction that $13+23^2+33^3 + \cdots + n3^n = \dfrac{3}{4}(3^n(2n-1)+1)$