Find a formula for $ 1\times3^0 + 3\times3^1 + 5\times3^2 + ... +(2n+1)\times3^n$.

Question

The original exercise is to find a formula for this and prove it via induction. However, I am having a problem deriving such a formula. How do you normally approach this types of problems, is it a matter of experience, guessing or something else? For n = 0,1,2,3 the sums are respectively, 1,10,55,244, but I am not able to find such a pattern which will help me figure out the formula. PS: the author considers 0 to be a part of the natural numbers.

Answer 1

It is a mixture of all of them. You can try the following approach: let $$ S_n = \sum_{k=0}^{n}(2k+1)3^k.$$ Then: $$ S_{n+1}-3\,S_n = \sum_{k=0}^{n+1}(2k+1)3^k-\sum_{k=1}^{n+1}(2k-1)3^k = 1+2\sum_{k=1}^{n+1}3^k=3^{n+2}-2$$ and: $$ S_n = (S_n-3S_{n-1})+3(S_{n-1}-3S_{n-2})+9(S_{n-2}-3S_{n-3})+\ldots $$ leads to: $$ S_n=\sum_{k=0}^{n}(2k+1)\,3^k = n 3^{n+1}+1.$$

Answer 2

The sum is given by $$\sum_{k=1}^{n+1} (2k-1)3^{k-1} = 2\sum_{k=1}^{n+1} k \cdot 3^{k-1} - \sum_{k=1}^{n+1} 3^{k-1}$$ Recall that $$\sum_{k=1}^{n+1} x^k = \dfrac{x(x^{n+1}-1)}{x-1}$$ and $$\sum_{k=1}^{n+1} k \cdot x^{k-1} = \dfrac{(n+1)x^{n+2}-(n+2)x^{n+1}+1}{(x-1)^2}$$ I trust you can now finish it off.

Answer 3

Exactly, so the answers are :

(1) Sum (i=0 to n) 3^n = (3^(n+1)-1)/2

(2) Sum (i=0 to n) n*3^n = 3*(2*n*3^n-3^n+1)/4