Thread: Prove by mathematical induction

Prove by induction or strong induction that every even integer greater than 30 can be written in the form:

So I started off with my basis step this way:




So the basis step is true.

Then follows the inductive step:



Then I realise I am stuck here. I don't know how I should move on from here. The usual inductions are like I could find something that looks like the basis step and then replace the k+1 part with the basis claim. But I can't do this in this one.

Thanks for any help.

Originally Posted by xEnOn

Prove by induction or strong induction that every even integer greater than 30 can be written in the form:

So I started off with my basis step this way:




So the basis step is true.

Then follows the inductive step:



Then I realise I am stuck here. I don't know how I should move on from here. The usual inductions are like I could find something that looks like the basis step and then replace the k+1 part with the basis claim. But I can't do this in this one.

Thanks for any help.

Why is your basis step n = 16 ???
It states that n must be greater than 30.

Oh... I somewhat see where you're going. I think strong induction is in order.

Actually, before this, I had my n=32. But I got stuck as soon as I started my basis step because I don't know how I can get even number from n=32. Making it n+2 does work all the time if n happens to be an odd number then adding 2 will still make it an odd number.

So I tried the other way to have it as 2n instead. But I still get stuck.

Oh... I somewhat see where you're going. I think strong induction is in order.

Why is strong induction better? I feel like I get stuck too because I need to keep finding the correct x and y for all the different values of even integer n to make sure the P(16) and P(17)...P(n) are all true. And I don't know at which P(##) I can stop to be considered proved.

Originally Posted by xEnOn

Prove by induction or strong induction that every even integer greater than 30 can be written in the form:

So I started off with my basis step this way:




So the basis step is true.

Then follows the inductive step:



Then I realise I am stuck here. I don't know how I should move on from here. The usual inductions are like I could find something that looks like the basis step and then replace the k+1 part with the basis claim. But I can't do this in this one.

Thanks for any help.

How about this. I'll work with your idea of replacing n with 2n. You have the base case so let there be a value of n, k, such that the theorem holds. We need to show that the theorem holds for k + 1.

What does it mean for the theorem to hold? Well we need to prove that x', y' in Z+ exist. So let's start with

2k = 6x + 10y

We want to find x' and y' such that
2(k + 1) = 6x' + 10y'

2k + 2 = 6x' + 10y'

(6x + 10y) + 2 = 6x' + 10y' <--Using the hypothesis step

2 = 6(x' - x) + 10(y' - y)

We need to show that there exist x' and y' such that the above equation holds and x' and y' are integers. I'll leave this step to you.

-Dan

I went on and did this:


Does this consider proven? I found it a little weird. I used the x=2 and y=2 which I found in the basis step in this and it turns out that n=34. So n really did advance from 32 to 34 and 34 is also an even number. But does this tell anything and is it even correct?

Originally Posted by xEnOn

I went on and did this:


Does this consider proven? I found it a little weird. I used the x=2 and y=2 which I found in the basis step in this and it turns out that n=34. So n really did advance from 32 to 34 and 34 is also an even number. But does this tell anything and is it even correct?

Well, I was simply going to say that if we have x' - x = -3 and y' - y = 2 then 2 = 6(x' - x) + 10(y' - y). Thus x' - x = -3 is an integer and thus x' is an integer. Similar for y'. Thus integers x' and y' exist such that 2(k + 1) = 6x' + 10y' and the theorem is proved.

As I was typing this I thought of a potential problem. x' and y' must be positive integers according to the problem statement. With x' - x = -3 we would have to show also that x' = x - 3 > 0 which means we need to prove that x > 3. Have to think about that one.

-Dan

Edit: Recall that you reset the problem so it was 2n = 6x + 10y. so your next to last step should be 2 = 2n - 32. However if you use this line of reasoning then all you've shown is that the theorem holds for 2n = 34. Not for all n.

ahh.. Thanks!
So x' and y' can be another integer number so long as and to consider the theorem proved, right?

For the positive integer problem, can we say that we only consider the case when x'=4 and x=1, and y'=3 and y=1?
So the equation will become and both x' and y' must be positive integers now. But would this miss out any possible cases that also proves the theorem?

Originally Posted by xEnOn

Prove by induction or strong induction that every even integer greater than 30 can be written in the form:

So I started off with my basis step this way:




So the basis step is true.

Then follows the inductive step:



Then I realise I am stuck here. I don't know how I should move on from here. The usual inductions are like I could find something that looks like the basis step and then replace the k+1 part with the basis claim. But I can't do this in this one.

Thanks for any help.

You could also have proceeded thus...


P(k)

n=2k=2(3x+5y) is a positive integer


P(k+1)

m=2(k+1)=2(3x+5y+1) is also a positive integer.

Show that P(k+1) will be true if P(k) is true


Proof

m=2(3x+5y)+2

which is even if n is even.

Test for the base case...

Originally Posted by xEnOn

ahh.. Thanks!
So x' and y' can be another integer number so long as and to consider the theorem proved, right?

For the positive integer problem, can we say that we only consider the case when x'=4 and x=1, and y'=3 and y=1?
So the equation will become and both x' and y' must be positive integers now. But would this miss out any possible cases that also proves the theorem?

Well, x and y are set by 2k = 6x + 10y, so we can't adjust those. Good thought, though.

Yeah, I was afraid something like this would happen. 36 = 6(1) + 10(3). So x does not have to be greater than 3. I'm not sure where, but there must be a flaw in my work. Sorry about that.

-Dan

Edit: Side thought. I wonder if x and y are unique? Hmmmm...