# Is this a valid inductive proof?

Tags:
1. Nov 26, 2016

### mustang19

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: Nov 26, 2016
2. Nov 26, 2016

### PeroK

I would say you have proved nothing.

This should be homework.

3. Nov 26, 2016

### mustang19

Can you find an inductive proof that all numbers divisible by 4 are divisible by 2?

4. Nov 26, 2016

### mustang19

• (*) 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: Nov 26, 2016
5. Nov 26, 2016

### PeroK

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.

6. Nov 26, 2016

### Staff: Mentor

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.
That's what you have to show.

7. Nov 26, 2016

### mustang19

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: Nov 26, 2016
8. Nov 26, 2016

### Staff: Mentor

Your approach in post #4 is good, especially after the recent edit.
This step could get some more justification or a reference to something shown before.
The last 3 steps don't make sense, but you don't need them. The first line is your assumption for the inductive step.

9. Nov 26, 2016

### PeroK

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.

10. Nov 26, 2016

### mustang19

I edited my post to include the distributive property. The tiny loops are not "0=", they are just artifacts.

11. Nov 26, 2016

### PeroK

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$