Question

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 3^k pieces of candy to the k^th trick-or-treater to arrive. Children love you, dentists despise you.

(a) Expressed in summation notation (using a Σ), what is c_n, 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: c_n = (3ⁿ⁺¹ - 3) / 2 

Answer 1

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