- #1
MarkFL
Gold Member
MHB
- 13,284
- 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:
$$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.
(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.
