Problem 36

ThePerfectHacker · #1 $Old$ September 4th, 2007, 07:04 PM

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.

janvdl · #2 $Old$ September 5th, 2007, 05:39 AM

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?

SkyWatcher · #3 $Old$ September 5th, 2007, 06:27 AM

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!

SkyWatcher · #4 $Old$ September 5th, 2007, 07:28 AM

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)

Soroban · #5 $Old$ September 5th, 2007, 11:40 AM

Hello, ThePerfectHacker!

Drag your cursor between the asterisks.

Quote:

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.

*

Quote:

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.)

*

kezman · #6 $Old$ September 6th, 2007, 11:41 AM

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

ThePerfectHacker · #7 $Old$ September 6th, 2007, 03:42 PM

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?

janvdl · #8 $Old$ September 6th, 2007, 03:56 PM

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?

kezman · #9 $Old$ September 6th, 2007, 05:09 PM

Quote:

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$

SkyWatcher · #10 $Old$ September 7th, 2007, 12:44 PM

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?

albi · #11 $Old$ September 10th, 2007, 04:21 PM

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....

albi · #12 $Old$ September 10th, 2007, 04:50 PM

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....

ThePerfectHacker · #13 $Old$ September 10th, 2007, 07:28 PM

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.

albi · #14 $Old$ September 11th, 2007, 04:33 AM

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.

albi · #15 $Old$ September 11th, 2007, 04:37 AM

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?