How Does Mathematical Induction Work?

[ineedhelpnow]

I don't know what forum to post this under. PLEASE HELP ME THOUGH!

Principle of Mathematical induction:
Let $S_n$ be a statement concerning the positive integer n. Suppose that,
$S_n$ is true.
For any positive integer k, k $\le$ n, if $S_k$ is true, then $S_{k+1}$ is also true.
Then $S_n$ is true for every positive integer value of x.

Proof by Mathematical induction
Step 1- prove that the statement is true for n=1
Step 2 - show that, for any positive integer k, k $\le$ n, if $S_k$ is true, then $S_{k+1}$ is also true

$3+9+27...+3^n=\frac{1}{2}(3^{n+1}-3)$

Please help

 

[MarkFL]

I'll move this thread to the Pre-Calculus forum when I am finished posting...

I would choose to write the induction hypothesis $P_n$ as:

$$\sum_{k=1}^n\left[3^k\right]=\frac{3}{2}\left(3^n-1\right)$$

So, we first want to verify that $P_1$ is true. So put a 1 everywhere you see $n$ in $P_n$ and see if you get a true statement, an identity.

 

[ineedhelpnow]

Whenever we do these kind of questions he wants us to prove $S_1$ and $S_{k+1}$ and $S_k$

 

[MarkFL]

I use $P_1$, $P_n$ and $P_{n+1}$. They mean the same thing as the symbols you are using, just substitute accordingly. :D

 

[Prove It]

I don't know what forum to post this under. PLEASE HELP ME THOUGH!

Principle of Mathematical induction:
Let $S_n$ be a statement concerning the positive integer n. Suppose that,
$S_n$ is true.
For any positive integer k, k $\le$ n, if $S_k$ is true, then $S_{k+1}$ is also true.
Then $S_n$ is true for every positive integer value of x.

Proof by Mathematical induction
Step 1- prove that the statement is true for n=1
Step 2 - show that, for any positive integer k, k $\le$ n, if $S_k$ is true, then $S_{k+1}$ is also true

$3+9+27...+3^n=\frac{1}{2}(3^{n+1}-3)$

Please help

Induction is not necessary...

$\displaystyle \begin{align*} S &= 3 + 9 + 27 + \dots + 3^n \\ 3S &= 9 + 27 + 81 + \dots + 3^n + 3^{n + 1} \\ 3S + 3 &= 3 + 9 + 27 + 81
+ \dots + 3^n + 3^{n + 1} \\ 3S + 3 &= S + 3^{n + 1} \\ 3S - S &= 3^{n + 1} - 3 \\ 2S &= 3^{n + 1} - 3 \\ S &= \frac{1}{2} \left( 3^{n + 1} - 3 \right) \end{align*}$

Of course, if you recognise this is a geometric series, you could just use a geometric series formula as well (which is derived in the same way as I did with this particular series).

 

[MarkFL]

Induction is not necessary...

$\displaystyle \begin{align*} S &= 3 + 9 + 27 + \dots + 3^n \\ 3S &= 9 + 27 + 81 + \dots + 3^n + 3^{n + 1} \\ 3S + 3 &= 3 + 9 + 27 + 81
+ \dots + 3^n + 3^{n + 1} \\ 3S + 3 &= S + 3^{n + 1} \\ 3S - S &= 3^{n + 1} - 3 \\ 2S &= 3^{n + 1} - 3 \\ S &= \frac{1}{2} \left( 3^{n + 1} - 3 \right) \end{align*}$

Of course, if you recognise this is a geometric series, you could just use a geometric series formula as well (which is derived in the same way as I did with this particular series).

If we wish to disregard the instructions regarding the use of induction ((Angel)), we could also use the difference equation:

$$S_{n}-S_{n-1}=3^n$$

Seeing we have a characteristic root of $r=1$ and given the inhomogeneous solution based on the term on the right, we can say the general solution is:

$$S_n=c_1+c_2\cdot3^n$$

Using the initial values, we obtain:

$$S_1=c_1+3c_2=3$$

$$S_2=c_1+9c_2=12$$

Solving this system, we find:

$$c_1=-\frac{3}{2},\,c_2=\frac{3}{2}$$

Thus:

$$S_n=\frac{3}{2}\left(3^n-1\right)$$

 

[Prove It]

If we wish to disregard the instructions regarding the use of induction ((Angel))

Of course we do, in my opinion we should only resort to induction if all else fails - to me it just doesn't seem as elegant as a direct proof (or even a contrapositive or contradiction proof) :P

 

[Deveno]

Suppose we wish to prove the statement:

For all $n \in \Bbb N$: (here, we will take $\Bbb N$ to start with 1)

$\displaystyle \sum_{k = 1}^n 3^n = \dfrac{1}{2}(3^{n+1} - 3)$.

If we succeed in proving this is true for $n = 1$, and that whenever it is true for some natural number $m$, it is true for the next natural number $m+1$, we may safely conclude that the set of natural numbers it is true for, is all of them (this is one of the fundamental facts about the natural numbers, known as the Peano Principle of Mathematical Induction).

Now $3^1 = 3 = \dfrac{1}{2}(6) = \dfrac{1}{2}(9 - 3) = \dfrac{1}{2}(3^2 - 3)$.

Suppose:

$\displaystyle \sum_{k = 1}^m 3^m = \dfrac{1}{2}(3^{m+1} - 3)$. (*)

Then:

$\displaystyle \sum_{k = 1}^{m+1} 3^{m+1} = \left(\displaystyle \sum_{k = 1}^m 3^m\right) + 3^{m+1}$

$= \dfrac{1}{2}(3^{m+1} - 3) + 3^{m+1}$ (by our supposition (*))

We need to show that this is equal to $\dfrac{1}{2}(3^{(m+1)+1} - 3) = \dfrac{1}{2}(3^{m+2} - 3)$.

So...

$\dfrac{1}{2}(3^{m+1} - 3) + 3^{m+1} = \dfrac{1}{2}(3^{m+1} - 3) + \dfrac{1}{2}(2\cdot 3^{m+1})$

$= \dfrac{1}{2}[(1 + 2)3^{m+1} - 3] = \dfrac{1}{2}(3\cdot3^{m+1} - 3) = \dfrac{1}{2}(3^{m+2} - 3)$, QED.I hope it is clear what I did, here. I broke the sum for the $m+1$ case, into two terms, the sum of the first $m$ terms, and the one extra term we get in the $m+1$ case.

I then substituted what was in the parentheses, what we assumed as true, by (*).

The rest is just "algebra", simplifying what we obtained, until it was in the "shape" we wanted.

 

[ineedhelpnow]

we HAVE to do it by induction. Whenever we get a problem like this we have to do my MI.

 

[Deveno]

we HAVE to do it by induction. Whenever we get a problem like this we have to do my MI.

That may be what your class requires. Understand, however, that class is just "practice", eventually you are tasked with "using anything that works".

Usually, the point of such exercises is not to "prove the statement" (theorem). It's to make you more FAMILIAR with how induction can be used.

The "classic example" often used to illustrate how this is done is to prove:

$1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$.

You should do this, you'll probably have to use this fact to evaluate a Riemann sum, someday.

 

[ineedhelpnow]

yeah but if he sees us doing it another he'll freak out and on the test he says to do it EXACTLY like he does otherwise he won't accept it.

 

[Deveno]

While you are in HIS class, to get HIS grade, you have to follow HIS instructions. Personally, I have always felt this is somewhat of an abuse of power by instructors, but there is little you or I can do about that.

You are free, however, to fail the class if you so choose. This may not be in your best interests.

But seeing as how you "have" to prove this by induction, this has already been shown to you in this thread. As I indicated before, your instructor probably doesn't intend to make you learn induction on a personal whim, but because he knows you will need to be proficient at it later.

A lot of times, with "induction proofs", it's not the "proving" part that people struggle with, it's the "induction" part: students don't understand the "nuts and bolts" of how an induction proof works. Sometimes, there's no easy remedy for this, but to keep at it (using examples) until it "clicks".

 

[MarkFL]

I'll even rewrite my original help to use the symbols you know:

I would choose to write the induction hypothesis $S_k$ as:

$$\sum_{j=1}^k\left[3^j\right]=\frac{3}{2}\left(3^k-1\right)$$

So, we first want to verify that $S_1$ is true. So put a 1 everywhere you see $k$ in $S_k$ and see if you get a true statement, an identity.

 

[ineedhelpnow]

i don't mind learning it has way i just don't like it when teachers limit it like that because you don't become familiar with other ways of doing it. I don't mind doing it HIS way but because Prove It said that we didn't have to do it by mathematical induction, I was saying that we had to. soooooo...yeah

 

[ineedhelpnow]

is this correct?

$S_n:3+9+27...+3^n=\frac{1}{2}(3^{n+1}-3)$$S_1:3^1=\frac{1}{2}(3^{1+1}-3)$

$S_1:3=\frac{1}{2}(3^2-3)$

$S_1:3=\frac{1}{2}(9-3)$

$S_1:3=\frac{1}{2}(6)$

$S_1:3=3$Suppose $n=k$ is true

$S_K:3+9+27...+3^k=\frac{1}{2}(3^{k+1}-3)$$S_{k+1}=3+9+27...+3^{k+1}=\frac{1}{2}(3^{k+1+1}-3)$

$S_{k+1}=3+9+27...+3^{k+1}=\frac{1}{2}(3^{k+2}-3)$

So $S_{k+1}$ is true when $S_k$ is true, so $S_n$ is true for $\forall$ $n \epsilon \mathbb{N}$

 

[MarkFL]

You can't simply replace $k$ with $k+1$ as your inductive step. You need to start with the induction hypothesis:

$$\sum_{j=1}^k\left[3^j\right]=\frac{3}{2}\left(3^k-1\right)$$

And now, you need to derive $S_{k+1}$ from this. What do you think would make the left side of the hypothesis exactly what it needs to be?

 

[ineedhelpnow]

i don't know. i haven't seen it done that way before.

 

[Deveno]

is this correct?

$S_n:3+9+27...+3^n=\frac{1}{2}(3^{n+1}-3)$$S_1:3^1=\frac{1}{2}(3^{1+1}-3)$

$S_1:3=\frac{1}{2}(3^2-3)$

$S_1:3=\frac{1}{2}(9-3)$

$S_1:3=\frac{1}{2}(6)$

$S_1:3=3$Suppose $n=k$ is true

$S_K:3+9+27...+3^k=\frac{1}{2}(3^{k+1}-3)$$S_{k+1}=3+9+27...+3^{k+1}=\frac{1}{2}(3^{k+1+1}-3)$

$S_{k+1}=3+9+27...+3^{k+1}=\frac{1}{2}(3^{k+2}-3)$

So $S_{k+1}$ is true when $S_k$ is true, so $S_n$ is true for $\forall$ $n \epsilon \mathbb{N}$

No, you haven't proven anything. All you've done is STATED $S_k$, and $S_{k+1}$, you have not shown how $S_{k+1}$ is a CONSEQUENCE of $S_k$. Just because $S_k$ is true (maybe only for that one $k$, we don't know...yet), we have no idea if $S_{k+1}$ is true.

However, we ARE allowed to use $S_k$ in proving $S_{k+1}$. So:

$3 + 9 + 27 + \cdots + 3^{k+1} = $ (the is the "left-hand side" of the equality we wish to establish)

$(3 + 9 + 27 + \cdots + 3^k) + 3^{k+1}$ (all we've done here is put parentheses around the first $k$ terms).

Now, the "stuff in parentheses" is the left-hand side of the equation we are calling $S_k$. So we can substitute in the RIGHT-hand side of that equation (since they are equal).

That will give us an expression "we haven't seen before", that we need to simplify:

$[\frac{1}{2}(3^{k+1} - 3)] + 3^{k+1}$.

The next step is to see if we can "re-arrange" this somehow, to make the right-hand side of the equation $S_{k+1}$.

Try it.

 

[ineedhelpnow]

yeah i know something is wrong with the $S_{k+1}$ i don't really understand that step

 

[MarkFL]

i don't know. i haven't seen it done that way before.

Try adding $$3^{k+1}$$ to both sides, and then simplify, and you should get $S_{k+1}$. Then you will have completed your proof by induction. :D

 

[Deveno]

On the first line I show some math, ending with an equals sign, and a comment in parentheses. We're trying to prove this is equal to something else (the right-hand side of the statement $S_{k+1}$).

But it is certainly equal to what I wrote on the second line, I just "grouped" the sum in a way that suggests how we should USE $S_k$.

On the third line, I have "plugged in" what we are allowed to assume, in assuming $S_k$ is true.

Your task now, is to show that this equals what we'd like it to be (the right-hand side of $S_{k+1}$).EDIT: An inductive proof, is like a line of dominoes, each one knocks over the next one.

Let's start with the simplest example:

$3 = \frac{1}{2}(6) = \frac{1}{2}(9 - 3) = \frac{1}{2}(3^2 - 3)$.

Now let's look at what happens with $n = 2$:

$3 + 9 = 12 = \frac{1}{2}(24) = \frac{1}{2}(27 - 3) = \frac{1}{2}(3^3 - 3)$.

Now let's look at $n = 3$:

$3 + 9 + 27 = 39 = \frac{1}{2}(78) = \frac{1}{2}(81 - 3) = \frac{1}{2}(3^4 - 3)$.

It certainly looks like there's a pattern. Let's look at $n = 3$ a bit more closely:

The first two terms, are the same ones we have in the $n = 2$ case.

So we can replace $3 + 9$ with the expression:

$\frac{1}{2}(3^3 - 3)$, both of these expressions are equal to 12.

That gives $\frac{1}{2}(3^3 - 3) + 27 = \frac{1}{2}(3^3 - 3) + \frac{1}{2}\cdot 54$

(27 = 54/2).

Ok, so let's take the fraction 1/2 "out front" and combine everything else:

$\frac{1}{2}(3^3 - 3) + \frac{1}{2}\cdot 54 = \frac{1}{2}(3^3 - 3 + 54)$.

Note that $54 = 2\cdot 27 = 2(3^3)$, so we have a $3^3$ term we can combine:

$\frac{1}{2}(3^3 - 3 + 54) = \frac{1}{2}(3^3 - 3 + 2\cdot 3^3) = \frac{1}{2}((1+2)3^3 - 3)$

Fortuitously, 1+2 = 3, so we get "an extra power of 3" we are subtracting from:

$\frac{1}{2}((1+2)3^3 - 3) = \frac{1}{2}(3\cdot3^3 - 3) = \frac{1}{2}(3^4 - 3)$.

Huh...that's the formula we're trying to establish for $n = 3$, and we can get there just using the formula for $n = 2$.

Now, we could repeat this, for every single natural number $n$, but it would take, like...forever.

 

[ineedhelpnow]

so what we want to end up with is what $S_k$ is equal to?

 

[Deveno]

so what we want to end up with is what $S_k$ is equal to?

You have two equations, one equation is NAMED $S_k$ (the equation we get summing $k$ powers of 3 on the left, and another formula on the right), and one equation is NAMED $S_{k+1}$.

Let's write them like so:

$S_k: A = B$

$S_{k+1}: C = D$

You wrote down $A,B,C,D$ correctly (you've identified what they are), but you haven't shown $C = D$ if $A = B$.

The general idea is to re-write $C$ as:

$C = A\text{ and something else}$

Since $A = B$ is what we're allowed to use, we get:

$C = B\text{ and something else}$

Then we need to show that $B\text{ and something else }$ actually turns out to be $D$.

 

[ineedhelpnow]

$S_{k+1}:$$(3+9+27...+3^k)+3^{k+1}=[\frac{1}{2}(3^{k+1}-3)]+3^{k+1}$

$S_{k+1}:$$3+9+27...+3^k=\frac{1}{2}(3^{k+1}-3)$

?

 

[Deveno]

$S_{k+1}:$$(3+9+27...+3^k)+3^{k+1}=[\frac{1}{2}(3^{k+1}-3)]+3^{k+1}$

$S_{k+1}:$$3+9+27...+3^k=\frac{1}{2}(3^{k+1}-3)$

?

The first line is a good starting point, you've "substituted in" what you can use from $S_k$.

I hope it's clear that $S_k$ is just a "name" so we don't have to keep writing cumbersome things like:

"The statement of the theorem for $n = k$".

I have no idea where you are going with the second line, and I suspect you don't, either.

Try looking at what I did for $n = 2$ and $n = 3$ a couple of posts ago, and see if you can "imitate" that.

 

[ineedhelpnow]

i subtracted $3^{k+1}$ from both sides but ill take it that's wrong

 

[Nono713]

As has been said before, induction works as follows. Let $S_k$ be a statement parameterised with a natural number $k$. If you can show that $S_1$ holds, and that $S_k$ implies $S_{k + 1}$ for any $k$ (actually, you may assume that it holds for all $n \leq k$, but for simple problems like these the weaker form is usually sufficient) then by induction you will have shown $S_k$ holds for all natural $k$.

Here your statement $S_k$ is:

$$S_k ~ : ~ 3 + 3^2 + \cdots + 3^k = \frac{1}{2} \left ( 3^{k + 1} - 3 \right )$$

So we first begin by showing it is true for $S_1$, i.e. with $k = 1$, and indeed:

$$\frac{1}{2} \left ( 3^2 - 3 \right ) = \frac{6}{2} = 3$$

Okay, part 1 done. Now we ASSUME that $k$ is any integer, and that the statement $S_k$ is true. In other words, we ASSUME that the following is true (it is given to us):

$$3 + 3^2 + \cdots + 3^k = \frac{1}{2} \left ( 3^{k + 1} - 3 \right )$$

We need to show that IF THIS IS TRUE, THEN $S_{k + 1}$ MUST ALSO BE TRUE, i.e. we must show that:

$$3 + 3^2 + \cdots + 3^k = \frac{1}{2} \left ( 3^{k + 1} - 3 \right ) ~ ~ ~ \stackrel{IMPLIES}{\implies} ~ ~ 3 + 3^2 + \cdots + 3^k + 3^{k + 1} = \frac{1}{2} \left ( 3^{(k + 1) + 1} - 3 \right )$$

We can show this as follows. First, start from our assumption:

$$3 + 3^2 + \cdots + 3^k = \frac{1}{2} \left ( 3^{k + 1} - 3 \right )$$

Now add $3^{k + 1}$ to each side (remember that if $x = y$, then $x + c = y + c$, i.e. $x = y$ implies $x + c = y + c$, and in fact the reverse is also true in this case, i.e. the two statements are equivalent - but for induction we do not need equivalence, only implication). We then get:

$$3 + 3^2 + \cdots + 3^k + 3^{k + 1} = \frac{1}{2} \left ( 3^{k + 1} - 3 \right ) + 3^{k + 1}$$

At this point the LHS is equal to the LHS of the statement we want to arrive at ($S_{k + 1}$), so we really just need to show that:

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

Once you have proven this, then you will have shown that $S_k$ implies $S_{k + 1}$, for any $k$ (we made no assumptions on the value of $k$ here, it could be any natural number). Therefore it follows logically that:

$$S_1 \implies S_2 \implies S_3 \implies \cdots$$

And we also know $S_1$ is true (we showed it earlier). Therefore $S_k$ is true for all natural numbers $k$. In order words, the equation holds for all natural numbers, and the proof by induction is complete.

Does this make it clearer? Do you understand the logical steps taken and why induction works? Can you complete the missing part necessary to show that $S_k \implies S_{k + 1}$ (the "inductive step")?