Prove by mathematical induction

Printable View

April 28th 2011, 09:27 AM
xEnOn

Prove by mathematical induction

Prove by induction or strong induction that every even integer $n$ greater than 30 can be written in the form: $n=6x+10y, \; \; where \; x,y \in \mathbb{Z}^{+}$

So I started off with my basis step this way:
$Basis \; Step: \; n=16$
$2n=6x+10y$
$2(16)=6\cdot2 + 10\cdot 2$
$32=6\cdot2 + 10\cdot 2$
So the basis step is true.

Then follows the inductive step:
$Inductive \; Step: \; Assume \; 2(k+1)=6x+10y \;is \; true \; for \; k=n$
$2k+2=6x+10y$

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.
April 28th 2011, 09:34 AM
TheChaz

Quote:

Originally Posted by xEnOn

Prove by induction or strong induction that every even integer $n$ greater than 30 can be written in the form: $n=6x+10y, \; \; where \; x,y \in \mathbb{Z}^{+}$

So I started off with my basis step this way:
$Basis \; Step: \; n=16$
$2n=6x+10y$
$2(16)=6\cdot2 + 10\cdot 2$
$32=6\cdot2 + 10\cdot 2$
So the basis step is true.

Then follows the inductive step:
$Inductive \; Step: \; Assume \; 2(k+1)=6x+10y \;is \; true \; for \; k=n$
$2k+2=6x+10y$

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.
April 28th 2011, 09:51 AM
xEnOn

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.

Quote:

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.
April 28th 2011, 09:59 AM
topsquark

Quote:

Originally Posted by xEnOn

Prove by induction or strong induction that every even integer $n$ greater than 30 can be written in the form: $n=6x+10y, \; \; where \; x,y \in \mathbb{Z}^{+}$

So I started off with my basis step this way:
$Basis \; Step: \; n=16$
$2n=6x+10y$
$2(16)=6\cdot2 + 10\cdot 2$
$32=6\cdot2 + 10\cdot 2$
So the basis step is true.

Then follows the inductive step:
$Inductive \; Step: \; Assume \; 2(k+1)=6x+10y \;is \; true \; for \; k=n$
$2k+2=6x+10y$

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
April 28th 2011, 10:20 AM
xEnOn

I went on and did this:
http://quicklatex.com/cache3/ql_214c...d2b0679_l3.png

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?
April 28th 2011, 10:42 AM
topsquark

Quote:

Originally Posted by xEnOn

I went on and did this:
http://quicklatex.com/cache3/ql_214c...d2b0679_l3.png

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.
April 28th 2011, 11:37 AM
xEnOn

ahh.. Thanks!
So x' and y' can be another integer number so long as ${x}'-x=-3$ and ${y}'-y=2$ 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 $2=6(x' - 1) + 10(y' - 1)$ and both x' and y' must be positive integers now. But would this miss out any possible cases that also proves the theorem?
April 28th 2011, 12:09 PM
Archie Meade

Quote:

Originally Posted by xEnOn

Prove by induction or strong induction that every even integer $n$ greater than 30 can be written in the form: $n=6x+10y, \; \; where \; x,y \in \mathbb{Z}^{+}$

So I started off with my basis step this way:
$Basis \; Step: \; n=16$
$2n=6x+10y$
$2(16)=6\cdot2 + 10\cdot 2$
$32=6\cdot2 + 10\cdot 2$
So the basis step is true.

Then follows the inductive step:
$Inductive \; Step: \; Assume \; 2(k+1)=6x+10y \;is \; true \; for \; k=n$
$2k+2=6x+10y$

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...
April 28th 2011, 01:06 PM
topsquark

Quote:

Originally Posted by xEnOn

ahh.. Thanks!
So x' and y' can be another integer number so long as ${x}'-x=-3$ and ${y}'-y=2$ 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 $2=6(x' - 1) + 10(y' - 1)$ 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...