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

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.

• Hint - do you know how to sum $3^n$ and $n3^n$. If you do, you can put that knowledge together. Apr 22, 2015 at 21:41

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.$$
• I hope that you don't mind, but $1+2\sum_{k=1}^{n+1}3^k =3^{n+2}-2$, so I took the liberty of correcting the erratum. Apr 22, 2015 at 21:55
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.