MHB How can we prove the recursive definition of $S$ by induction?

[MarkFL]

I was recently sent the following question via PM (which we discourage here), so I thought I would start a thread and help here (and give the OP a link to this thread). Here's the question:

(a) We can observe that we may write:

$$2\cdot\sum_{k=0}^{n}\left(3^k\right)=2\cdot\sum_{k=0}^{n-1}\left(3^k\right)+2\cdot3^n$$

Hence:

$$S(n)=S(n-1)+2\cdot3^n$$

Now, if we were to derive a closed form for $S(n)$ from the above linear inhomogeneous recursion, we would observe that the homogeneous solution is:

$$h_n=c_1$$

And, we would be looking for a particular solution of the form:

$$p_n=A3^n$$

So, to use the method of undetermined coefficients, we would substitute $p_n$ into the recursion to get:

$$A3^n-A3^{n-1}=2\cdot3^n$$

Divide through by $3^{n-1}$:

$$3A-A=6\implies A=3$$

Thus:

$$p_n=3^{n+1}$$

Hence, by the principle of superposition, we find the general solution to be:

$$S(n)=h_n+p_n=3^{n+1}+c_1$$

Now, to determine the parameter $c_1$, we find:

$$S(1)=2(1+3)=8=3^{1+1}+c_1=9+c_1\implies c_1=-1$$

And so we have:

$$S(n)=3^{n+1}-1$$

This agrees with the induction hypothesis we are to prove for part (b).

(b) State the induction hypothesis $$P_n$$:

$$2\cdot\sum_{k=0}^{n}\left(3^k\right)=3^{n+1}-1$$

Show the base case $P_1$ is true:

$$2\cdot\sum_{k=0}^{1}\left(3^k\right)=3^{1+1}-1$$

$$2(3^0+3^1)=3^{1+1}-1$$

$$8=8\quad\checkmark$$

The base case is true, so as our induction step, we may add $2\cdot3^{n+1}$ to each side of $P_n$:

$$2\cdot\sum_{k=0}^{n}\left(3^k\right)+2\cdot3^{n+1}=3^{n+1}-1+2\cdot3^{n+1}$$

One the left, incorporate the added term within the sum while on the right combine like terms:

$$2\cdot\sum_{k=0}^{n+1}\left(3^k\right)=3\cdot3^{n+1}-1$$

$$2\cdot\sum_{k=0}^{n+1}\left(3^k\right)=3^{(n+1)+1}-1$$

We have derived $P_{n+1}$ from $P_n$, thereby completing the proof by induction.

 

[HallsofIvy]

Did the person who sent it to you say why? There does not appear to be any question asked.

 

[MarkFL]

Did the person who sent it to you say why? There does not appear to be any question asked.

The question is in an image hot-linked to a free image hosting site...and I know from experience that they don't always show up, so I will type it out:

---

2.) Let $S$ be the function defined over $\mathbb{N}$ by:

$$S(n)=2\times\sum_{k=0}^n3^k$$

(a) Give the recursive definition of $S$.

(b) Prove the following statement by induction:

for all $n\in\mathbb{N}$, $S(*n)=3^{n+1}-1$​