Is this a valid inductive proof?

[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

 

[PeroK]

I would say you have proved nothing.

This should be homework.

 

[mustang19]

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?

 

[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.

 

[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.

 

[mfb]

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.

4(k+1)%2 = 0

That's what you have to show.

 

[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

 

[mfb]

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.

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.

 

[PeroK]

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.

 

[mustang19]

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.

 

[PeroK]

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##