# Thread: Recursion and Induction

1. 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:

$\displaystyle 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:

$\displaystyle 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:

$\displaystyle h_n=c_1$

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

$\displaystyle p_n=A3^n$

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

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

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

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

Thus:

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

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

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

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

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

And so we have:

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

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

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

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

Show the base case $P_1$ is true:

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

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

$\displaystyle 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$:

$\displaystyle 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:

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

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

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

Originally Posted by HallsofIvy
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$

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•