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

3pointonefour
Badges: 15
Rep:
?
#1
Report Thread starter 10 months ago
#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
reply
RDKGames
Badges: 20
Rep:
?
#2
Report 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
reply
DFranklin
Badges: 18
Rep:
?
#3
Report 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: s\neq 1. 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
3pointonefour
Badges: 15
Rep:
?
#4
Report Thread starter 10 months ago
#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: s\neq 1. 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
reply
Nabopolassar
Badges: 13
Rep:
?
#5
Report 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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top

University open days

  • Regent's University London
    Postgraduate Open Evening Postgraduate
    Thu, 19 Sep '19
  • Durham University
    Pre-Application Open Days Undergraduate
    Fri, 20 Sep '19
  • Loughborough University
    Undergraduate Open Day Undergraduate
    Fri, 20 Sep '19

What's your favourite genre?

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%

Watched Threads

View All