- #1
MarkFL
Gold Member
MHB
- 13,288
- 12
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.
(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.