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

#1
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
10 months ago
#2
(Original post by 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?
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.
0
10 months ago
#3
(Original post by 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 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.
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
#4
(Original post by 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.
Wow quite an elegant proof, never thought I'd use a proof by contradiction. Does the principle of strong induction also have a similar proof?
0
10 months ago
#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
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• Regent's University London
Thu, 19 Sep '19
• Durham University
Fri, 20 Sep '19
• Loughborough University
Fri, 20 Sep '19

### Poll

Join the discussion

Rock (115)
24.78%
Pop (108)
23.28%
Jazz (20)
4.31%
Classical (23)
4.96%
Hip-Hop (87)
18.75%
Electronic (37)
7.97%
Indie (74)
15.95%