Results 1 to 15 of 16

- September 4th 2007, 05:04 PM #1

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

## Problem 36

1. Let be a non-increasing sequence so that . Prove that .

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

2. Given a positive integer define a -partition to be a sum of positive integers which sum to . For example, . The following are -partitions. and and . Notice that are considered distinct*. Say you a given a specific . And given a specific value of , can you find the total number of -partitions of this integer, with a formula?** Now try to see how many partitions (again not counting order) exist for a given integer (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.

- September 5th 2007, 03:39 AM #2

- September 5th 2007, 04:27 AM #3

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

- September 5th 2007, 05:28 AM #4

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

- September 5th 2007, 09:40 AM #5

- Joined
- May 2006
- From
- Lexington, MA (USA)
- Posts
- 12,028
- Thanks
- 846

Hello, ThePerfectHacker!

Drag your cursor between the asterisks.

2. Given a positive integer , define a -partition

to be a sum of positive integers which sum to .

For example, .

The following are -partitions: .

Notice that are considered distinct.*****

Say you are a given a specific and given a specific value of .

Can you find the total number of -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 .

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

*

- September 6th 2007, 09:41 AM #6

- September 6th 2007, 01:42 PM #7

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

- September 6th 2007, 01:56 PM #8

- September 6th 2007, 03:09 PM #9

- September 7th 2007, 10:44 AM #10

- Joined
- Jan 2006
- Posts
- 56

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?

- September 10th 2007, 02:21 PM #11

- Joined
- Jan 2006
- From
- Gdansk, Poland
- Posts
- 117

- September 10th 2007, 02:50 PM #12

- Joined
- Jan 2006
- From
- Gdansk, Poland
- Posts
- 117

## Let's try this way...

1. Suppose there exists k where . But then for . So . Thus the corresponding series does not converge which contradicts assumptions.

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

So we have for some n, end arbitrary chosen . What is more there are infinitly many elements with this property.

3. Now let us assume that converges. From 2. we have subsequence where .

So we get

Because is arbitrary we can put . Then we get:

---

So now we should prove that converges....

Or maybe go to sleep....

- September 10th 2007, 05:28 PM #13

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

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 rather consider . Since the series is convergent by the Cauchy criterion it means for all . So if then it means . Since the sequence is non-increasing it means for . Also for we have . This means . Q.E.D.

Note: This problem gives us a elegant way to show the divergence of the harmonic series.

- September 11th 2007, 02:33 AM #14

- 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 . From Cauchy condition we have (as you noticed): . Now we simply take and to get .

That means this positive sequence converges to 0.

- September 11th 2007, 02:37 AM #15

- Joined
- Jan 2006
- From
- Gdansk, Poland
- Posts
- 117