Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - Problem 36

  1. #1
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9

    Problem 36

    1. Let \{a_n\} be a non-increasing sequence so that \sum_{n=1}^{\infty}a_n < \infty. Prove that \lim \ na_n = 0.

    And this problem is for the younger kids. (So give them a chance to solve it).


    2. Given a positive integer n define a k-partition to be a sum of k positive integers which sum to n. For example, n=10. The following are 4-partitions. 10 = 4+4+2+2 and 10 = 2+2+4+4 and 10 = 1+1+1+7. Notice that 2+2+4+4\mbox{ and }4+4+2+2 are considered distinct*. Say you a given a specific n. And given a specific value of k, can you find the total number of k-partitions of this integer, with a formula?** Now try to see how many partitions (again not counting order) exist for a given integer n (the answer is really supprising).
    Hint: Review your Combinatorics formula for this one.



    *)This is done to simplify this problem. When these are not considered distinct this forms a problem from number theory called the "partition problem". It is a very complicated problem.

    **)The problem is not whether you can. But rather how you can. If it was the later the answer would be "yes" turning this problem into a worthless problem.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by ThePerfectHacker View Post
    2. Given a positive integer n define a k-partition to be a sum of k positive integers which sum to n. For example, n=10. The following are 4-partitions. 10 = 4+4+2+2 and 10 = 2+2+4+4 and 10 = 1+1+1+7. Notice that 2+2+4+4\mbox{ and }4+4+2+2 are considered distinct*. Say you a given a specific n. And given a specific value of k, can you find the total number of k-partitions of this integer, with a formula?** Now try to see how many partitions (again not counting order) exist for a given integer n (the answer is really supprising).

    Hint: Review your Combinatorics formula for this one.
    \frac{(n + k - 1)!}{k!(n - 1)!}

    So if n = 10 and using 4-partitions(including repetitions), then we will have 715 possibilities.

    \frac{(10 + 4 - 1)!}{4!((10 - 1)!)} = 715


    Am i even close to correct?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    your close to correct!
    but an other matter is to prove it!
    first check (close to correct)=correct whith little numbers
    then try to find a connection whith your (or a near one) anwser and the probleme
    i suggest you to try to find an equivalent problem that you can resolve!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    as 4+4+2+2=12 and not 10
    i supose that PerfectHacker mean 'increasing suite Un' instead of nonincreasing:
    consider the suite Un=(-1^n)/sqr(n) and you would then had a contre-exemple!

    by the way in the second problem i suppose 0 is considered like a positive integer (wich it is I think)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,707
    Thanks
    627
    Hello, ThePerfectHacker!

    Drag your cursor between the asterisks.


    2. Given a positive integer n, define a k-partition
    to be a sum of k positive integers which sum to n.

    For example, n=10.
    The following are 4-partitions: 10 = 4+4+2+2,\; 10 = 2+2+4+4,\;10 = 1+1+1+7.
    Notice that 2+2+4+4\mbox{ and }4+4+2+2 are considered distinct. *

    Say you are a given a specific n and given a specific value of k.
    Can you find the total number of k-partitions of this integer, with a formula?

    * This is done to simplify this problem.
    When these are not considered distinct, this forms a problem from number theory
    called the "partition problem", a very complicated problem.
    Yes, it is. I investigated it years ago.
    *
    Consider a board n inches long.
    It is marked with n-1 inch-marks.

    We will cut it (on the inch-marks) into k pieces.
    So we will make k-1 cuts.

    There are: C(n-1, k-1) ways to choose the cuts.


    *



    Now try to see how many partitions (again not counting order)
    exist for a given integer n.
    *
    We have a board n units long with n-1 inch-marks.

    For each of the n-1 inch-marks, there are two choices: cut or don't cut.

    Therefore, there are: 2^{n-1} possible partitions.

    (This includes an intact, uncut board.)


    *
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member kezman's Avatar
    Joined
    Jul 2006
    Posts
    92
    Thanks
    2
    A_n+1/a_n<1 so with dalembert and knowing that a_n -> 0 then lim (n+1).a_n+1/n.a_n < 1 then lim n.a_n = 0
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by kezman View Post
    A_n+1/a_n<1 so with dalembert and knowing that a_n -> 0 then lim (n+1).a_n+1/n.a_n < 1 then lim n.a_n = 0
    What?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    But the combinatorics formula has already been proven. And that is the formula used to calculate stuff like this anyway. Did i go wrong somewhere in the understanding of this problem?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member kezman's Avatar
    Joined
    Jul 2006
    Posts
    92
    Thanks
    2
    What?
    A_n = n.a_n
    a_n \to 0 because is a convergent series.
    and a_{n+1}/a_n<1
    then \lim \frac{A_{n+1}}{A_n} =   \lim \frac{(n+1)}{n}. \frac{a_{n+1}}{{a_n}} < 1
    so A_n \to 0
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jan 2006
    Posts
    56
    Quote Originally Posted by janvdl View Post
    But the combinatorics formula has already been proven. And that is the formula used to calculate stuff like this anyway. Did i go wrong somewhere in the understanding of this problem?
    your above awnser to the question was close to corect but not correct:
    i suppose you ment to express a certain combinatory formula
    but you did it wrong (i cannot see your formula while writing but take k=n and you ll ,see there is a problem)
    so I suppose you misunderstood the problem in your own percular way because you've got something that looks like the arythmetique expression of the solution (strange is'nt it)
    what's interresting in this problem is the combinatorial expression of the solution and of course and mainly why?
    an other way to pose the problem (but i think this is not the way that is nearer the solution) is 'how many way can you fill N indistinct balls in K distinct boxes'
    would it helping you?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jan 2006
    From
    Gdansk, Poland
    Posts
    117

    Not exactly

    Quote Originally Posted by kezman View Post
    A_n = n.a_n
    a_n \to 0 because is a convergent series.
    and a_{n+1}/a_n<1
    then \lim \frac{A_{n+1}}{A_n} =   \lim \frac{(n+1)}{n}. \frac{a_{n+1}}{{a_n}} < 1
    so A_n \to 0
    Let us consider the series \sum x_n = \sum \frac{1}{n^2}. We can see that for this one we get: \lim \frac{x_{n+1}}{x_n} = 1.
    What is more we know that the series converges.

    So for the convergent series \sum a_n you can't conclude that \lim \frac{a_{n+1}}{a_n}<1.

    The other part is wrong too....
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Jan 2006
    From
    Gdansk, Poland
    Posts
    117

    Let's try this way...

    1. Suppose there exists k where a_k. But then a_n \leq a_k for n > k. So \lim a_n \leq a_k < 0. Thus the corresponding series does not converge which contradicts assumptions.

    2. So now we know that a_n is a positive sequence. So let us assume that a_n \geq \frac{\epsilon}{n}. By the 'comparison test' (or whatever it is called in English) we have that series \sum a_n does not converge which again contradicts the assumptions.

    So we have a_n < \frac{\epsilon}{n} for some n, end arbitrary chosen \epsilon > 0. What is more there are infinitly many elements with this property.

    3. Now let us assume that n a_n converges. From 2. we have subsequence n_k where a_{n_k} < \frac{\epsilon}{n_k}.

    So we get 0 \leq \lim n a_n = \lim n_k a_{n_k} \leq \epsilon

    Because \epsilon is arbitrary we can put \epsilon \rightarrow 0 . Then we get:

    \lim n a_n = 0

    ---
    So now we should prove that n a_n converges....

    Or maybe go to sleep....
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    The combinatorics question was answered by Soroban. Here is the solution to the series question. This question comes from my homework on Real Analysis last semester.

    For any \epsilon > 0 rather consider \frac{\epsilon}{2} > 0. Since the series is convergent by the Cauchy criterion it means \left| \sum_{k=m}^n a_n \right|  = \sum_{k=m}^n a_n < \frac{\epsilon}{2} for all n\geq m\geq N. So if m=N then it means a_N+a_{N+1}+...+a_n < \frac{\epsilon}{2}. Since the sequence is non-increasing it means (n-N)a_n = \underbrace{a_n+...+a_n}_{n-N} \leq a_{N}+...+a_n < \frac{\epsilon}{2} for n\geq 2N. Also for n\geq 2N we have n = 2n - n \leq 2n -2N = 2(n-N). This means na_n \leq 2a_n(n-N) < \epsilon. Q.E.D.


    Note: This problem gives us a elegant way to show the divergence of the harmonic series.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jan 2006
    From
    Gdansk, Poland
    Posts
    117
    Hm, isn't it too early to post the solution, and make the other people have no fun?

    I would like to do this more elegant simply taking \epsilon > 0. From Cauchy condition we have (as you noticed): (k-l)a_l < a_l + a_{l+1} + \ldots + a_k < \epsilon . Now we simply take  k = 2n and l = n to get na_n < \epsilon.

    That means this positive sequence converges to 0.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Jan 2006
    From
    Gdansk, Poland
    Posts
    117
    Quote Originally Posted by ThePerfectHacker View Post
    Note: This problem gives us a elegant way to show the divergence of the harmonic series.
    How do you think one should do that?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Search Tags


/mathhelpforum @mathhelpforum