Is this a valid inductive proof?

  • Thread starter mustang19
  • Start date
  • Tags
    proof
In summary: The distributive property can be used to simplify the equation.4(k+1) = 4k + 4 = 0 + 0 = 0 \mod 2## is simpler, where ##4k = 0 \mod 2## and ##4 = 0 \mod 2## follow from your inductive hypothesis and from the result for ##n =1##.The distributive property can be used to simplify the equation.
  • #1
mustang19
75
4
Mentor note: moved to the homework section

Claim: all numbers divisible by 4 are divisible by 2.

Premise: let p(n) return 4n, I.e., the function covers all numbers divisible by four.

Reasoning:

Let n equal 1 in the base case

P(n) is divisible by 2

P(n+1) is divisible by 2

By induction all n are divisible by 2

QED
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
I would say you have proved nothing.

This should be homework.
 
  • Like
Likes mustang19
  • #3
PeroK said:
I would say you have proved nothing.

This should be homework.
Can you find an inductive proof that all numbers divisible by 4 are divisible by 2?
 
  • #4
  • (*) For all n, 4n%2=0

  • Let n = 1. Then:

    • 4n%2 = 0
    So (*) works for n = 1.

    Assume, for n = k, that (*) holds; that is, that

    4k%2
  • = 4%2 times k%2 by distributive property
  • = 0 times k%2
  • = 0

  • Let n = k + 1.

    • 4(k+1)%2
    • = (4k+4)%2 by distributive property
    • = 4k%2 + 4%2 by distributive property
    • = 4k%2 + 0
    • = 4k%2
    • = 4%2 times k%2 by distributive property
    • = 0 times k%2
    • = 0
    Then (*) works for n = k + 1.
 
Last edited:
  • #5
That's better, but it's still short of a rigorous proof, if that's what you are trying to do.

One problem is that your inductive step doesn't really use the inductive hypothesis.
You can do this because the proof doesn't need induction.
 
  • Like
Likes mustang19
  • #6
mustang19 said:
Claim: all numbers divisible by 4 are divisible by 2.

Premise: let p(n) return 4n, I.e., the function covers all numbers divisible by four.

Reasoning:

Let n equal 1 in the base case

P(n) is divisible by 2

P(n+1) is divisible by 2

By induction all n are divisible by 2

QED
Following the same logic, all numbers divisible by 4 are smaller than 10.
Let n equal 1 in the base case.
P(n) is smaller than 10
P(n+1) is smaller than 10.
By induction all numbers divisible by 4 are smaller than 10.

This problem is not well suited for induction as the direct proof is much easier, even in the induction step.
mustang19 said:
4(k+1)%2 = 0
That's what you have to show.
 
  • Like
Likes mustang19
  • #7
I know that, I just want to use an inductive proof. Can anyone find any for this problem or at least be specific?

I edited the proof to show how 4k%2 = 0
 
Last edited:
  • #8
Your approach in post #4 is good, especially after the recent edit.
0 = (4k+4)%2
0 = 4k%2 + 4%2
This step could get some more justification or a reference to something shown before.
mustang19 said:
0= 4k%2
0= 4%2 times k%2
0= 0 times k%2
0= 0
The last 3 steps don't make sense, but you don't need them. The first line is your assumption for the inductive step.
 
  • Like
Likes mustang19
  • #9
mustang19 said:
I know that, I just want to use an inductive proof. Can anyone find any for this problem or at least be specific?

I edited the proof to show how 4k%2 = 0
You need to justify why ##4(k+1)## is divisible by 2. If you claim this is obvious, then there is no purpose to the proof, as this is entirely what you are trying to prove.
 
  • Like
Likes mustang19
  • #10
PeroK said:
You need to justify why ##4(k+1)## is divisible by 2. If you claim this is obvious, then there is no purpose to the proof, as this is entirely what you are trying to prove.

I edited my post to include the distributive property. The tiny loops are not "0=", they are just artifacts.
 
  • #11
mustang19 said:
I edited my post to include the distributive property. The tiny loops are not "0=", they are just artifacts.
I think ##4(k+1) = 4k + 4 = 0 + 0 = 0 \mod 2## is simpler, where ##4k = 0 \mod 2## and ##4 = 0 \mod 2## follow from your inductive hypothesis and from the result for ##n =1##
 
  • Like
Likes mustang19

Related to Is this a valid inductive proof?

What is an inductive proof?

An inductive proof is a method of mathematical reasoning that uses a series of observations or examples to prove a statement for all possible cases.

How is an inductive proof different from a deductive proof?

In an inductive proof, we make a generalization based on specific examples, while in a deductive proof, we start with general statements and use logical reasoning to reach a specific conclusion.

What makes an inductive proof valid?

An inductive proof is valid if the conclusion drawn from a series of examples or observations holds true for all possible cases.

Can an inductive proof be used to prove any statement?

No, an inductive proof can only be used to prove statements that can be generalized from a finite number of observations or examples. It cannot be used to prove statements that require infinite or continuous cases.

What are some common mistakes to avoid in an inductive proof?

Some common mistakes to avoid in an inductive proof include using biased or limited examples, jumping to conclusions without sufficient evidence, and assuming causation from correlation. It is important to carefully examine all possible cases and ensure that the conclusion is logically connected to the examples or observations.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
366
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
920
  • Precalculus Mathematics Homework Help
Replies
3
Views
719
  • Precalculus Mathematics Homework Help
Replies
27
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
Back
Top