Induction Questions

• Mar 14th 2010, 09:58 AM
moocav
Induction Questions
I have quite a few questions and so i just made it an image. Also attached.
Induction Questions
Only need help with questions 2 and 5

Oh and so far my lecturer has taught well-ordering, strong induction and simple induction. But I could only follow simple induction... the other two I'm quite clueless about >< Though tell me which method is best for each question.

Attempts
Question 2
I have no clue to how to start it..
all i've done is
24 = 7 + 7 + 5 + 5
25 = 5 + 5 + 5 + 5 + 5
26 = 7 + 7 + 7 + 5
27 = 7 + 5 + 5 + 5 + 5
28 = 7 + 7 + 7 + 7
29 = 7 + 7 + 5 + 5 + 5
no idea what to do next

Question 5
Show that n/t - 1/(q+1) is positive and numerator is less than n
where t = nq + r with 0 < r < n

(get common denominator then expand and simplify)
n/t - 1/(q+1)
= n(q + 1)/[t(q+1)] - t/[t(q+1)]
= [n(q+1) - t] / [t(q+1)]
= [nq - t + n] / [t(q+1)]

t = nq + r
nq - t = -r

hence n/t - 1/(q+1)
= [n-r] / [t(q+1)]

from 0 < r < n
n > r therefore n - r > 0 (proved that numerator is positive)
and since r > 0 then n - r < n (proved that numerator is < n)

I'm not sure where to go from here

Please someone help me however you can..
• Mar 14th 2010, 10:47 AM
tonio
Quote:

Originally Posted by moocav
I have quite a few questions and so i just made it an image. Also attached.
Induction Questions
Only need help with questions 2 and 5

Oh and so far my lecturer has taught well-ordering, strong induction and simple induction. But I could only follow simple induction... the other two I'm quite clueless about >< Though tell me which method is best for each question.

Attempts
Question 2
I have no clue to how to start it..
all i've done is
24 = 7 + 7 + 5 + 5
25 = 5 + 5 + 5 + 5 + 5
26 = 7 + 7 + 7 + 5
27 = 7 + 5 + 5 + 5 + 5
28 = 7 + 7 + 7 + 7
29 = 7 + 7 + 5 + 5 + 5
no idea what to do next

This was already practically solved some weeks ago...(Angry)...**sigh**...take any natural number $n>29\Longrightarrow \exists k\in\mathbb{N}\,\,s.t.\,\,\,24\leq n-5k\leq 29$ (why? Think!) , so $n-5k$ can be written as a sum of 5's and 7's...and voila!

Question 5
Show that n/t - 1/(q+1) is positive and numerator is less than n
where t = nq + r with 0 < r < n

(get common denominator then expand and simplify)
n/t - 1/(q+1)
= n(q + 1)/[t(q+1)] - t/[t(q+1)]
= [n(q+1) - t] / [t(q+1)]
= [nq - t + n] / [t(q+1)]

t = nq + r
nq - t = -r

hence n/t - 1/(q+1)
= [n-r] / [t(q+1)]

from 0 < r < n
n > r therefore n - r > 0 (proved that numerator is positive)
and since r > 0 then n - r < n (proved that numerator is < n)

I'm not sure where to go from here

Please someone help me however you can..
...so by the inductive hypothesis the number $\frac{n}{t}-\frac{1}{q+1}$ can be written as a sum of no more than $n-1$ fractions with 1 as numerator, and thus...(!!!)