plz find the attached file.

Printable View

- May 30th 2007, 04:10 AMaamirpk4Mathematical Induction
**plz find the attached file.**

- May 30th 2007, 08:24 AMJhevon
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 1

- prove P(1) is true

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

so here is the first:

Let for all integers

Then , which is true.

So is true

Assume is true for some , we show that is true.

So we have:

add the term to both sides, we get:

=

.................................................. ..................................

.................................................. ..................................

.................................................. ..................................

.................................................. ..................................

.................................................. ..................................

.................................................. ..................................

.................................................. ..................................

Thus, is true.

Therefore is true for all by the method of Mathemtaical Induction

If there is any step that confuses you, say so - May 30th 2007, 09:30 AMJhevon
Here's the second question:

**Prove is irrational**

**Proof:**Assume to the contrary that is rational

Then is rational as well.

But is only rational if is rational. So is rational and so is rational.

Assume is rational.

Then for , and we may further assume that is in lowest terms

This means that

Which means

But this means 21 divides , which means 21 divides (can you prove this?)

Since 21 divides , for

So

So

So

But this means 21 divides , so 21 divides

So we can write for some

Therefore,

But this is a contradiction, since we assumed is in lowest terms. So we have that is NOT rational, therefore is NOT rational. Thus, is irrational.

QED.

What I did with 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 is irrational.**

**Proof:**Consider the equation

By the Rational Roots Theorem, the ONLY rational solutions to this equation are

But is a solution to the above equation. Therefore, 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 is rational, then is rational, and 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, 10:47 AMThePerfectHacker
- May 30th 2007, 02:20 PMSoroban
Hello, aamirpk4!

Had to do some acrobatics for #3 . . .

Quote:

3) Prove by induction that: . .for

The base case is .

. . Is . . . yes!

Assume is true: .

Multiply both sides by 3: .

. . and we have: . .**[1]**

And now a short detour . . .

. . Since , we know that: .

. . Multiply both sides by

. . Hence, we have: .

Combined with [1], we have: .

We have proved . . . The inductive proof is complete.

- May 30th 2007, 03:21 PMKrizalid