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

AI Thread Summary
The discussion focuses on proving the recursive definition of the function S, defined as S(n) = 2 × ∑(3^k) for k=0 to n. The recursive relation is established as S(n) = S(n-1) + 2 × 3^n, leading to a closed form solution of S(n) = 3^(n+1) - 1. The proof by induction is structured with a base case showing that P_1 holds true, followed by an induction step that successfully derives P_(n+1) from P_n. The discussion concludes with the confirmation that the induction proof is complete and valid.
MarkFL
Gold Member
MHB
Messages
13,284
Reaction score
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:

419089e327ebd61d79d892db74c94a8f.png


(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.
 
Mathematics news on Phys.org
Did the person who sent it to you say why? There does not appear to be any question asked.
 
HallsofIvy said:
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$​
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top