induction (1 Viewer)
- Thread starter bobohappy
- Start date
1. By inspection: RHS = 2^n * 3^n * 4^n * ... * (n+1)^n
LHS = 2^n * 3^(n-1) * 4^(n-1) * 5^(n-2) * 6^(n-2) * ... * (2n-1) * 2n
= 2^n * [3^(n-1) * 2n] * [4^(n-1) * (2n-1)] * [5^(n-1) * (2n-2)^2] * [4^(n-1) * (2n-3)^2] * ...
Arranged this way you cna see that each part of the LHS is no less that the right hand side and atleast one of them is greater (n >=2), so LHS> RHS
2. Expanding the left hand side will give you 2^n terms (1 + x1 + x2 + ... + xn + x1x2 + x1x3 + ... + x1xn + x2x3 + x2x4 + ... + x2xn + .... + x1x2x3...xn), the product of these terms is equal to
(x1*x2*x3*...*xn)^(2^(n-1)) = 1 then apply the AM-Gm inequality (prove it if you need to you only need it for the case where the number of terms is a power of 2)
3. think you mean 0 <= xk < 1 instead of 0<= xk < 0. This should be a simple induction. remember that the LHS is always between 0 and 1.
4. You sure you got the sign the correct way round? for x > 0
let f(x) = (1 + x + x^2 + ... + x^ n )/ (1 + x + x^2 + ... + x^(n+1) )
= 1 + [ x^n / (1 + x + x^2 + ... + x^(n+1))]
= 1 + 1/[1/x + 1/x^2 + 1/x^3 + ... + 1/x^n]
now it is pretty clear that 1/x, 1/x^2, ... 1/x^n all decrease as x increases and they are all positive , their sum also decreases hence f(x) is an increasing function. It follows that
(1+ a + a^2 + ... + a^(n+1))/(1+ a + a^2 + ... + a^(n)) > (1+ b + b^2 + ... + b^(n+1)) / (1+ b + b^2 + ... + b^(n))
LHS = 2^n * 3^(n-1) * 4^(n-1) * 5^(n-2) * 6^(n-2) * ... * (2n-1) * 2n
= 2^n * [3^(n-1) * 2n] * [4^(n-1) * (2n-1)] * [5^(n-1) * (2n-2)^2] * [4^(n-1) * (2n-3)^2] * ...
Arranged this way you cna see that each part of the LHS is no less that the right hand side and atleast one of them is greater (n >=2), so LHS> RHS
2. Expanding the left hand side will give you 2^n terms (1 + x1 + x2 + ... + xn + x1x2 + x1x3 + ... + x1xn + x2x3 + x2x4 + ... + x2xn + .... + x1x2x3...xn), the product of these terms is equal to
(x1*x2*x3*...*xn)^(2^(n-1)) = 1 then apply the AM-Gm inequality (prove it if you need to you only need it for the case where the number of terms is a power of 2)
3. think you mean 0 <= xk < 1 instead of 0<= xk < 0. This should be a simple induction. remember that the LHS is always between 0 and 1.
4. You sure you got the sign the correct way round? for x > 0
let f(x) = (1 + x + x^2 + ... + x^ n )/ (1 + x + x^2 + ... + x^(n+1) )
= 1 + [ x^n / (1 + x + x^2 + ... + x^(n+1))]
= 1 + 1/[1/x + 1/x^2 + 1/x^3 + ... + 1/x^n]
now it is pretty clear that 1/x, 1/x^2, ... 1/x^n all decrease as x increases and they are all positive , their sum also decreases hence f(x) is an increasing function. It follows that
(1+ a + a^2 + ... + a^(n+1))/(1+ a + a^2 + ... + a^(n)) > (1+ b + b^2 + ... + b^(n+1)) / (1+ b + b^2 + ... + b^(n))
Last edited:
addikaye03
The A-Team
2. For 
we have 
, therefore 
. Assume true up to 
. For 
, group 
and 
into one, so we can apply the induction hypothesis:
.
Unfortunately,
is not guaranteed. So we need an idea. Well, since 
, there must be some 
and some 
. Redo all of the above with 
instead of 
. We reach that last desirable inequality, equivalent to 
, which now is true.
This solution is courtesy of members on AoPS and is what i thought clearly not my solution
we have , therefore . Assume true up to . For , group and into one, so we can apply the induction hypothesis: . Unfortunately,
is not guaranteed. So we need an idea. Well, since , there must be some and some . Redo all of the above with instead of . We reach that last desirable inequality, equivalent to , which now is true.This solution is courtesy of members on AoPS and is what i thought clearly not my solution
Last edited:
addikaye03
The A-Team
3.Our base case is which is just 
which is true.
ok so suppose that it is true for n=a-1. Now we want to prove that the statement is true for n=a.
So we have our a numbers
and it is true that
by our induction hypothesis. We want to prove that
Notice that both sides (especially the LHS) are less than or equal to 1. This is true for the LHS because each product is positive and less than or equal to 1.
Therefore,
adding our two inequalities (1) and (2) gives the desired result.
equality is achieved when n or n-1 of the
are equal to 0.
This can be seen from setting both (1) and (2) as equalities.
This solution is courtesy of members on AoPS and is what i thought clearly not my solution
which is just which is true. ok so suppose that it is true for n=a-1. Now we want to prove that the statement is true for n=a.
So we have our a numbers
and it is true that
by our induction hypothesis. We want to prove that Notice that both sides (especially the LHS) are less than or equal to 1. This is true for the LHS because each product is positive and less than or equal to 1.
Therefore,
adding our two inequalities (1) and (2) gives the desired result.
equality is achieved when n or n-1 of the
are equal to 0. This can be seen from setting both (1) and (2) as equalities.
This solution is courtesy of members on AoPS and is what i thought clearly not my solution
Last edited:
addikaye03
The A-Team
4.
Equality occurs when
. Otherwise, note that
so without loss of generality we can assume that
. We cross multiply to get
When
we have
We can prove that
by induction on 
, noting that
If
, then by the lemma,
so the desired inequality follows from induction.
Got a feeling induction wasn't intended for any of these Q btw
EDIT: Geometric Series and all the (x-1) cancel out would be the normal approach no?
This solution is courtesy of members on AoPS and is what i thought clearly not my solution
Equality occurs when
. Otherwise, note that so without loss of generality we can assume that
. We cross multiply to get When
we have We can prove that
by induction on , noting that If
, then by the lemma, so the desired inequality follows from induction.
Got a feeling induction wasn't intended for any of these Q btw
EDIT: Geometric Series and all the (x-1) cancel out would be the normal approach no?
This solution is courtesy of members on AoPS and is what i thought clearly not my solution
Last edited:
K
khorne
Guest
Yo dawg, we heard you liked plagarism, so we put a plagiarised post in your plagiarisedpost, so you can plagiarise while you plagiarise:
Art of Problem Solving Forum
Art of Problem Solving Forum
Art of Problem Solving Forum
Art of Problem Solving Forum
Art of Problem Solving Forum
Art of Problem Solving Forum
Art of Problem Solving Forum
Art of Problem Solving Forum
addikaye03
The A-Team
umm.. i thought it was pretty clear that i asked them on AoPS. Consider the latex is from there, and has AoPS coding throughout the entire thing.
Post edited to make it clear. Was merely trying to help the OP, since there were no solutions for sometime
Last edited:
K
khorne
Guest
You didn't cite it, and then copied affinity into another thread, making you twice the berk.
addikaye03
The A-Team
Sourced in AoPS actually and it's cited now, i'm be more careful with citation of it in the future i guess, it's pretty obvious though
K
khorne
Guest
Lesson in citation: Done
