# Mathematical Induction

• May 30th 2007, 05:10 AM
aamirpk4
Mathematical Induction
plz find the attached file.
• May 30th 2007, 09:24 AM
Jhevon
Quote:

Originally Posted by aamirpk4
plz find the attached file.

here's the first. i want you to try the third question on your own, and post your solution.

this is how math. induction works.

we begin with some statement that depends on a set of integers, usually the whole set of natural numbers. to prove the statement is true by math. induction, we do the following procedure.

we prove that the statement is true for the first integer it is claimed to be true for, usually this is 1. so we find P(1) and show that the statement is true if we replace n with 1. if it's true, we are in good shape. this step is called the basis

next we move on to the inductive step or inductive hypothesis. in this step, we assume that the statement is true for some integer k which is greater than or equal to the base integer. and then we prove that if it's true for this term, then it will be true for the next term, that is, the k + 1 term.

so iduction in a nutshell:

given a statement P(n) for n $\geq$ 1

- prove P(1) is true
- assume P(k) is true for some k $\geq$ 1, and derive that P(k + 1) is true

so here is the first:

Let $P(n): " \frac {1}{1 \cdot 3} + \frac {1}{3 \cdot 5} + \frac {1}{5 \cdot 7} + ... + \frac {1}{(2n - 1)(2n + 1)} = \frac {n}{2n + 1}$ for all integers $n \geq 1 "$

Then $P(1): \frac {1}{(2(1) - 1)(2(1) + 1)} = \frac {1}{1 \cdot 3} = \frac {1}{2(1) + 1} = \frac {1}{3}$, which is true.

So $P(1)$ is true

Assume $P(k)$ is true for some $k \geq 1$, we show that $P(k + 1)$ is true.

So we have:

$P(k): \frac {1}{1 \cdot 3} + \frac {1}{3 \cdot 5} + \frac {1}{5 \cdot 7} + ... + \frac {1}{(2k - 1)(2k + 1)} = \frac {k}{2k + 1}$

add the $k + 1$ term to both sides, we get:

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

.................................................. .................................. $= \frac {k}{2k + 1} + \frac {1}{(2k + 1)(2k + 3)}$

.................................................. .................................. $= \frac {k(2k + 3) + 1}{(2k + 1)(2k + 3)}$

.................................................. .................................. $= \frac {2k^2 + 3k + 1}{(2k + 1)(2k + 3)}$

.................................................. .................................. $= \frac {(2k + 1)(k + 1)}{(2k + 1)(2k + 3)}$

.................................................. .................................. $= \frac {k + 1}{2k + 3}$

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

.................................................. .................................. $= P(k + 1)$

Thus, $P(k + 1)$ is true.

Therefore $P(n)$ is true for all $n \geq 1$ by the method of Mathemtaical Induction

If there is any step that confuses you, say so
• May 30th 2007, 10:30 AM
Jhevon
Quote:

Originally Posted by aamirpk4
plz find the attached file.

Here's the second question:

Prove $\sqrt {3} + \sqrt {7}$ is irrational

Proof: Assume to the contrary that $\sqrt {3} + \sqrt {7}$ is rational

Then $\left( \sqrt {3} + \sqrt {7} \right)^2 = 10 + 2 \sqrt {21}$ is rational as well.

But $10 + 2 \sqrt {21}$ is only rational if $2 \sqrt {21}$ is rational. So $2 \sqrt {21}$ is rational and so $\sqrt {21}$ is rational.

Assume $\sqrt {21}$ is rational.

Then $\sqrt {21} = \frac {a}{b}$ for $a,b \in \mathbb {Z} \mbox { , } b \neq 0$, and we may further assume that $\frac {a}{b}$ is in lowest terms

This means that $21 = \frac {a^2}{b^2}$

Which means $21 b^2 = a^2$

But this means 21 divides $a^2$, which means 21 divides $a$ (can you prove this?)

Since 21 divides $a$, $a = 21 m$ for $m \in \mathbb {Z}$

So $21 b^2 = a^2 \Longleftrightarrow 21 b^2 = \left( 21 m \right)^2$

So $21 b^2 = 21^2 m^2$

So $b^2 = 21 m^2$

But this means 21 divides $b^2$, so 21 divides $b$

So we can write $b = 21 n$ for some $n \in \mathbb {Z}$

Therefore, $\frac {a}{b} = \frac {21m}{21n} = \frac {m}{n}$

But this is a contradiction, since we assumed $\frac {a}{b}$ is in lowest terms. So we have that $\sqrt {21}$ is NOT rational, therefore $\sqrt {3} + \sqrt {7}$ is NOT rational. Thus, $\sqrt {3} + \sqrt {7}$ is irrational.

QED.

What I did with $\sqrt {21}$ is the standard way I was taught to prove something is irrational. I admit it is a beautiful method that makes you wonder how the guy that came up with it did come up with it, but I never really liked it. Another way to prove something is irrational was found in one of my other texts, I kind of like such a proof better. It goes like this.

Prove $\sqrt {21}$ is irrational.

Proof: Consider the equation $x^2 - 21 = 0$

By the Rational Roots Theorem, the ONLY rational solutions to this equation are $\pm 1 \mbox { , } \pm 3 \mbox { , and } \pm 7$

But $\sqrt {21}$ is a solution to the above equation. Therefore, $\sqrt {21}$ is not a rational number

QED

Of course, this is not a contradiction proof, but it's a good proof to know if you are not restricted to doing a particular kind of proof. As you can see, it's much shorter.

Also, you may be tempted to begin with, "if $\sqrt {3} + \sqrt {7}$ is rational, then $\sqrt {3}$ is rational, and $\sqrt {7}$ is rational." And then you would proceed to show that both are irrational, and come up with a contradiction. This would be wrong, as it is possible to add two irrational numbers and get a rational one (can you prove this?)
• May 30th 2007, 11:47 AM
ThePerfectHacker
Quote:

Originally Posted by Jhevon
Prove $\sqrt {3} + \sqrt {7}$ is irrational

Nothing wrong with your proof. You taken the Pythagorean version and modifed it well. But here is another one.

----
Here is another:

$\mbox{ Let }x=\sqrt{3}+\sqrt{7}$
Then,
$x^2 = 10 + 2\sqrt{21}$
$x^2-10 = 2\sqrt{21}$
$x^4 - 20x^2+100 = 84$
$x^4 - 20x^2 + 16 = 0$

By rational root theorem none of $\pm 1,\pm 2,\pm 4,\pm 8,\pm 16$ solves this.
So it has irrational real roots or complex.
• May 30th 2007, 03:20 PM
Soroban
Hello, aamirpk4!

Had to do some acrobatics for #3 . . .

Quote:

3) Prove by induction that: . $3^n < n!$ .for $n > 6.$

The base case is $n = 7$.
. . Is $3^7 \,<\,7!\:?\quad\Rightarrow\quad 2187 \,<\,5040$ . . . yes!

Assume $S(k)$ is true: . $3^k \,< \,k!$

Multiply both sides by 3: . $3\!\cdot\!3^k \:<\:3\!\cdot\!k!$

. . and we have: . $3^{k+1}\:<\:3\!\cdot\!k!$ . [1]

And now a short detour . . .

. . Since $k > 6$, we know that: . $3 \:<\:k+1$

. . Multiply both sides by $k!\!:\;\;3\cdot k! \:<\:(k+1)\cdot k!$

. . Hence, we have: . $3\!\cdot\!k! \:< \: (k+1)!$

Combined with [1], we have: . $3^{k+1} \:<\: 3\!\cdot\!k! \:<\: (k+1)!$

We have proved $S(k+1)$ . . . The inductive proof is complete.

• May 30th 2007, 04:21 PM
Krizalid
Quote:

Originally Posted by Jhevon
here's the first. i want you to try the third question on your own, and post your solution.

this is how math. induction works.

we begin with some statement that depends on a set of integers, usually the whole set of natural numbers. to prove the statement is true by math. induction, we do the following procedure.

we prove that the statement is true for the first integer it is claimed to be true for, usually this is 1. so we find P(1) and show that the statement is true if we replace n with 1. if it's true, we are in good shape. this step is called the basis

next we move on to the inductive step or inductive hypothesis. in this step, we assume that the statement is true for some integer k which is greater than or equal to the base integer. and then we prove that if it's true for this term, then it will be true for the next term, that is, the k + 1 term.

so iduction in a nutshell:

given a statement P(n) for n $\geq$ 1

- prove P(1) is true
- assume P(k) is true for some k $\geq$ 1, and derive that P(k + 1) is true

so here is the first:

Let $P(n): " \frac {1}{1 \cdot 3} + \frac {1}{3 \cdot 5} + \frac {1}{5 \cdot 7} + ... + \frac {1}{(2n - 1)(2n + 1)} = \frac {n}{2n + 1}$ for all integers $n \geq 1 "$

Then $P(1): \frac {1}{(2(1) - 1)(2(1) + 1)} = \frac {1}{1 \cdot 3} = \frac {1}{2(1) + 1} = \frac {1}{3}$, which is true.

So $P(1)$ is true

Assume $P(k)$ is true for some $k \geq 1$, we show that $P(k + 1)$ is true.

So we have:

$P(k): \frac {1}{1 \cdot 3} + \frac {1}{3 \cdot 5} + \frac {1}{5 \cdot 7} + ... + \frac {1}{(2k - 1)(2k + 1)} = \frac {k}{2k + 1}$

add the $k + 1$ term to both sides, we get:

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

.................................................. .................................. $= \frac {k}{2k + 1} + \frac {1}{(2k + 1)(2k + 3)}$

.................................................. .................................. $= \frac {k(2k + 3) + 1}{(2k + 1)(2k + 3)}$

.................................................. .................................. $= \frac {2k^2 + 3k + 1}{(2k + 1)(2k + 3)}$

.................................................. .................................. $= \frac {(2k + 1)(k + 1)}{(2k + 1)(2k + 3)}$

.................................................. .................................. $= \frac {k + 1}{2k + 3}$

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

.................................................. .................................. $= P(k + 1)$

Thus, $P(k + 1)$ is true.

Therefore $P(n)$ is true for all $n \geq 1$ by the method of Mathemtaical Induction

If there is any step that confuses you, say so

Hey Jhevon

If you wanna align, use

\begin{aligned}

\end{aligned}

Example:

\begin{aligned}
a&=b\\
a^2&=ab\\
a^2-b^2&=ab-b^2\\
(a+b)(a-b)&=b(a-b)
\end{aligned}

This yields


\begin{aligned}
a&=b\\
a^2&=ab\\
a^2-b^2&=ab-b^2\\
(a+b)(a-b)&=b(a-b)
\end{aligned}

This was, the LaTeX's contribution.