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.
Asked
Active
Viewed 88 times
0
-
3Hint - do you know how to sum $3^n$ and $n3^n$. If you do, you can put that knowledge together. – Mark Bennet Apr 22 '15 at 21:41
3 Answers
5
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.$$
Mark Viola
- 179,405
Jack D'Aurizio
- 353,855
-
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. – Mark Viola Apr 22 '15 at 21:55
-
3
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.
Adhvaitha
- 20,259
0
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