LinkBack URL
About LinkBackshey guys need help solving this question.
Use induction to prove that every positive integer24 can be written as the sum of 5's and 7's. Not sure how to proceed with this question. Thanks!
Originally Posted by jvignacio
hey guys need help solving this question.
Use induction to prove that every positive integer
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).
And the above suffices to show the claim (why?)
Tonio
For the inductive hypothesis, letand suppose that your claim holds for all
You want to prove thatcan be expressed as a sum of 5's and 7's.
ConsiderWhat can you say about it?
Shouldnt it beWhat Tonio has done is prove your base case (you will need strong induction for this).
For the inductive hypothesis, let
You want to prove that
Consider? I understand the base case not sure what you mean by
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).Shouldnt it be
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
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(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
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 assumedand that (IH) the statement holds for all
Consider n+1-5=n-4. As, 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.
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
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.
  |
