**There is a long line of eager children outside of your house for trick-or-treating, and with good reason! Word has gotten around that you will give out 3k pieces of candy to the kth trick-or-treater to arrive. Children love you, dentists despise you. (a) Expressed in summation notation (using a Σ), what is cn, the total amount of candy that you should buy to accommodate n children total? (b) Use induction to prove that the total amount of candy that you need is given by the closed-form solution: cn = (3n+1 - 3) / 2**

The **Answer to the Question**

is below this banner.

**Here's the Solution to this Question**

a)

$c_n=\displaystyle{\sum_{k=1}^n}3^k$

b)

for k=1

$c_1=3=\frac{3^2-3}{3}$

let

$c_n=\displaystyle{\sum_{k=1}^n}3^k=\frac{3^{n+1}-3}{2}$

then:

$c_{n+1}=\displaystyle{\sum_{k=1}^{n+1}}3^k=\displaystyle{\sum_{k=1}^n}3^k+3^{n+1}=\frac{3^{n+1}-3}{2}+3^{n+1}=\frac{3^{n+1}-3+2\cdot3^{n+1}}{2}=$

$=\frac{3\cdot3^{n+1}-3}{2}=\frac{3^{n+2}-3}{2}$