Math Help - proof by induction

1. proof by induction

hey guys need help solving this question.
Use induction to prove that every positive integer $\geq$ 24 can be written as the sum of 5's and 7's. Not sure how to proceed with this question. Thanks!

2. Originally Posted by jvignacio
hey guys need help solving this question.
Use induction to prove that every positive integer $\geq$ 24 can be written as the sum of 5's and 7's. Not sure how to proceed with this question. Thanks!

$24=2(7+5)$

$25=2\cdot 5=5+5$

$26=3\cdot 7 +5$

$27=7+4\cdot 5$

$28=4\cdot 7$

And the above suffices to show the claim (why?)

Tonio

3. Originally Posted by tonio
$24=2(7+5)$

$25=2\cdot 5=5+5$

$26=3\cdot 7 +5$

$27=7+4\cdot 5$

$28=4\cdot 7$

And the above suffices to show the claim (why?)

Tonio
What Tonio has done is prove your base case (you will need strong induction for this).

For the inductive hypothesis, let $n \geq 28$ and suppose that your claim holds for all $k \leq n$

You want to prove that $n+1$ can be expressed as a sum of 5's and 7's.

Consider $n+1-5$ What can you say about it?

4. Originally Posted by Yasen
What Tonio has done is prove your base case (you will need strong induction for this).

For the inductive hypothesis, let $n \geq 28$ and suppose that your claim holds for all $k \leq n$

You want to prove that $n+1$ can be expressed as a sum of 5's and 7's.

Consider $n+1-5$ What can you say about it?
Shouldnt it be $n \geq 24$? I understand the base case not sure what you mean by $n+1-5$

5. Originally Posted by jvignacio
Shouldnt it be $n \geq 24$? I understand the base case not sure what you mean by $n+1-5$
Tonio proved your statement holds for 24, 25, 26, 27, and 28. So what you need to do is prove it holds for all numbers greater than 28 (and as it holds for 24-28, these two together show your statement holds for all numbers greater than 24).

Do you know how to do strong induction? For it, you suppose that a statement P holds. Then, if (P(0) holds and (whenever P(k) holds for all $k \leq n$, then P(n+1) holds)), then P holds for all natural numbers.

In your case, we are amending this principle a little:

1. Instead of P(0), you have P(24)-P(28) (where P is the statement that the integer can be written as the sum of 5's and 7's).

2. In the assumption of the IH, instead of saying P(k) holds for all k<=n, we way it holds for all $24 \leq k \leq n$ (i.e. we remove the first couple of numbers)

3. As we have shown P(24)-P(28), all we need to do is "start" the inductive hypothesis from P(29) on - i.e., assume n is greater or equal to 28, and that P(k) holds for all $24 \leq k \leq n$. We want to show that P(n+1) holds.

If we can do this, then this principle would show us that (the following is an intuitive discourse):

from P(28) holds: apply IH with n=28, and get that P(29) holds.
from P(29) holds: apply IH with n=29, and get that P(30) holds,... etc. Hence it holds for all natural numbers greater than 28, and as we've shown it holds for 24-28, it holds for all greater than 24.

(end of discourse)

So, how do we do (2)?

We have assumed $n \geq 28$ and that (IH) the statement holds for all $24 \leq k \leq n$. How do we show that P(n+1) holds?

Consider n+1-5=n-4. As $n-4 \leq n$, what does our inductive hypothesis tell us about n-4? And what can we conclude about (n-4)+5=n+1?

This would conclude the induction, hence concluding the proof.

6. hey, i was trying to find an answer to this exact question, i have just started a course in discrete mathematics and are lecturers are pretty bad and don't really explain things well, we have been given this question in our first assignment and while i understand how to get the answer, i dont know how to properly set it out, i have never done strong induction before, so would you be able to write out the structure of teh answer to this quesiton, thanks

7. It would be a far more productive use of your time to actually sit down with your textbook and practice some of the examples (I suggest pp291-294). I somehow doubt that you'll be allowed forum access during the final exam. It would also be helpful to understand that you're studying a quite challenging topic; blaming the lecturers for your inability to understand is not going to help. If you're really having trouble, there are a variety of resources at your disposal. Speak to your tutors or visit the Nemeracy Centre.

Accept that you've been given a massive clue here, and move along. Begging for answers smacks of desperation.

PS, you've left your run a little late, haven't you? It's due in tomorrow.