0
$\begingroup$

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.

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

3 Answers 3

5
$\begingroup$

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.$$

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Mark Viola
    Apr 22, 2015 at 21:55
  • $\begingroup$ @Dr.MV: well done, I don't mind at all. $\endgroup$ Apr 22, 2015 at 21:57
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .