 #1
 6
 0
2 Induction Questions
I have quite a few questions and so i just made it an image. Also attached.
http://img411.imageshack.us/img411/1002/inductionforlife.jpg" [Broken]
Only need help with questions 2 and 5 now
Oh and so far my lecturer has taught wellordering, 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.
Refer to image
3. The Attempt at a Solution s
Question 2
I have no clue to how to start it..
All i have 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 now
[STRIKE]Question 3
I'm not sure if my method is correct but I've proved that when x = 0 and n = 1, x = 1 n = 2 are true. But I get stuck whilst proving n = k + 1
Let S_{n} be (1 + x)^{n} >= 1 + nx
For n = 1 and x = 0, S_{1} =
LHS = (1+0)^{1} = 1
RHS = 1 + (1)(0) = 1
Therfore LHS >= RHS Hence n = 1 is true.
Assume n = k is true
S_{k} > (1 + x)^{k} >= 1 + kx
For n = k + 1, S_{k+1} =
I know that I need to get to
(1 + x)^{k+1} >= 1 + (k+1)x
(1 + x)^{k} >= 1 + kx
(1 + x)^{k}(1 + x)^{1} >= (1 + kx)(1 + x)^{1} (multiplied both sides by (x + 1)
(1 + x)^{k+1} >= 1 + x + kx + kx^{2}
I can see that on the RHS there is 1 + x + kx I'm not sure what to do with it... hints/help?
Question 4 (Just needs checking)
Let S_{n} be ƒ_{1} + ƒ_{2} + ... + ƒ_{n} = ƒ_{n+2} 1
For n = 1, S_{1}
LHS = ƒ_{1} = 1
RHS = ƒ_{1+2}  1 = 2  1 = 1
LHS = RHS
Therefore n = 1 is true
Assume true for n = k
S_{k} > ƒ_{1} + ƒ_{2} + ... + ƒ_{k} = ƒ_{k+2} 1
For n = k + 1, S_{k+1} =
RHS = ƒ_{k+3}  1
LHS = ƒ_{1} + ƒ_{2} + ... + ƒ_{k} + ƒ_{k+1}
= ƒ_{k+2} 1 + ƒ_{k+1}
= ƒ_{k+2} + ƒ_{k+1}  1
= ƒ_{k+3}  1 (should I write any reason here? if yes..what should i write?)
= RHS
Hence n = k + 1 is true
By mathematical induction S_{n} is true for all positive integers n.
[/STRIKE]
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)
= [nr] / [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..
Thank you in advance!!
Homework Statement
I have quite a few questions and so i just made it an image. Also attached.
http://img411.imageshack.us/img411/1002/inductionforlife.jpg" [Broken]
Only need help with questions 2 and 5 now
Oh and so far my lecturer has taught wellordering, 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.
Homework Equations
Refer to image
3. The Attempt at a Solution s
Question 2
I have no clue to how to start it..
All i have 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 now
[STRIKE]Question 3
I'm not sure if my method is correct but I've proved that when x = 0 and n = 1, x = 1 n = 2 are true. But I get stuck whilst proving n = k + 1
Let S_{n} be (1 + x)^{n} >= 1 + nx
For n = 1 and x = 0, S_{1} =
LHS = (1+0)^{1} = 1
RHS = 1 + (1)(0) = 1
Therfore LHS >= RHS Hence n = 1 is true.
Assume n = k is true
S_{k} > (1 + x)^{k} >= 1 + kx
For n = k + 1, S_{k+1} =
I know that I need to get to
(1 + x)^{k+1} >= 1 + (k+1)x
(1 + x)^{k} >= 1 + kx
(1 + x)^{k}(1 + x)^{1} >= (1 + kx)(1 + x)^{1} (multiplied both sides by (x + 1)
(1 + x)^{k+1} >= 1 + x + kx + kx^{2}
I can see that on the RHS there is 1 + x + kx I'm not sure what to do with it... hints/help?
Question 4 (Just needs checking)
Let S_{n} be ƒ_{1} + ƒ_{2} + ... + ƒ_{n} = ƒ_{n+2} 1
For n = 1, S_{1}
LHS = ƒ_{1} = 1
RHS = ƒ_{1+2}  1 = 2  1 = 1
LHS = RHS
Therefore n = 1 is true
Assume true for n = k
S_{k} > ƒ_{1} + ƒ_{2} + ... + ƒ_{k} = ƒ_{k+2} 1
For n = k + 1, S_{k+1} =
RHS = ƒ_{k+3}  1
LHS = ƒ_{1} + ƒ_{2} + ... + ƒ_{k} + ƒ_{k+1}
= ƒ_{k+2} 1 + ƒ_{k+1}
= ƒ_{k+2} + ƒ_{k+1}  1
= ƒ_{k+3}  1 (should I write any reason here? if yes..what should i write?)
= RHS
Hence n = k + 1 is true
By mathematical induction S_{n} is true for all positive integers n.
[/STRIKE]
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)
= [nr] / [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..
Thank you in advance!!
Attachments

54.9 KB Views: 342
Last edited by a moderator: