# How to prove "Proof by Induction" by induction? Watch

Page 1 of 1

Go to first unread

Skip to page:

So I was given this problem after pestering my maths teacher for some hard questions and he won't help me. So can anyone help?

0

reply

Report

#2

(Original post by

So I was given this problem after pestering my maths teacher for some hard questions and he won't help me. So can anyone help?

**3pointonefour**)So I was given this problem after pestering my maths teacher for some hard questions and he won't help me. So can anyone help?

If he seeking you to explain how it works for general statements ?

P.S. If you want hard induction questions just tag me on the hard questions thread.

0

reply

Report

#3

**3pointonefour**)

So I was given this problem after pestering my maths teacher for some hard questions and he won't help me. So can anyone help?

(Original post by

Not sure what that's supposed to mean.

If he seeking you to explain how it works for general statements ?

P.S. If you want hard induction questions just tag me on the hard questions thread.

**RDKGames**)Not sure what that's supposed to mean.

If he seeking you to explain how it works for general statements ?

P.S. If you want hard induction questions just tag me on the hard questions thread.

Sketch: Suppose P(n) is a statement involving n, e.g. P(n) "the sum of the first n integers is n(n+1)/2", and you know P(1) is true, and "if P(n) is true, then P(n+1) is true" (i.e. the two things you normally show when doing an inductive proof).

We want to show P is true for all n.

Well, to prove by contradiction, suppose otherwise.

Then there's a non-empty set S of values where P(n) is false. Define s to be the

**smallest**element of S (*)

Claim: . Proof: exercise for OP

So, we can assume s > 1. Define p = s-1.

Then P(p) is true. So P(p+1) is true. So P(s) is true. (**) So s is

**not**an element of S, contradiction.

So P(n) is true for all n by contradiction.

Notes:

(*) This is either "obvious" or "not at all obvious" depending on how pedantic you want to be. Believe me, pre-degree-level you want to decide "it's obvious" here!

(**) These 3 statements about P require proof. Again, exercise for OP.

0

reply

(Original post by

I'm assuming he wants an actual proof of the principle.

Sketch: Suppose P(n) is a statement involving n, e.g. P(n) "the sum of the first n integers is n(n+1)/2", and you know P(1) is true, and "if P(n) is true, then P(n+1) is true" (i.e. the two things you normally show when doing an inductive proof).

We want to show P is true for all n.

Well, to prove by contradiction, suppose otherwise.

Then there's a non-empty set S of values where P(n) is false. Define s to be the

Claim: . Proof: exercise for OP

So, we can assume s > 1. Define p = s-1.

Then P(p) is true. So P(p+1) is true. So P(s) is true. (**) So s is

So P(n) is true for all n by contradiction.

Notes:

(*) This is either "obvious" or "not at all obvious" depending on how pedantic you want to be. Believe me, pre-degree-level you want to decide "it's obvious" here!

(**) These 3 statements about P require proof. Again, exercise for OP.

**DFranklin**)I'm assuming he wants an actual proof of the principle.

Sketch: Suppose P(n) is a statement involving n, e.g. P(n) "the sum of the first n integers is n(n+1)/2", and you know P(1) is true, and "if P(n) is true, then P(n+1) is true" (i.e. the two things you normally show when doing an inductive proof).

We want to show P is true for all n.

Well, to prove by contradiction, suppose otherwise.

Then there's a non-empty set S of values where P(n) is false. Define s to be the

**smallest**element of S (*)Claim: . Proof: exercise for OP

So, we can assume s > 1. Define p = s-1.

Then P(p) is true. So P(p+1) is true. So P(s) is true. (**) So s is

**not**an element of S, contradiction.So P(n) is true for all n by contradiction.

Notes:

(*) This is either "obvious" or "not at all obvious" depending on how pedantic you want to be. Believe me, pre-degree-level you want to decide "it's obvious" here!

(**) These 3 statements about P require proof. Again, exercise for OP.

0

reply

Report

#5

The whole point of it is that it's meant to be intuitive. I don't think there's really a mathematical proof of a proof, maybe you could write a logical step by step idk

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top