How to Use Pascal's Identity to Simplify a Combinatorial Proof

[pazo]

I cannot seem to understand how to do a combinatorial proof on this one.

1. The problem statement: all variables and given/known data
Prove that for all positive numbers n, n₁,n₂,n_k, where 2 [tex]\leq[/tex] k [tex]\leq[/tex] n, and [tex]\sum_{i=1}^k n_i = n [/tex] the following is true
[tex]
\newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}
\colv{n+1}{2} < \colv{n_1+1}{2} + \colv{n_2+1}{2} + ...+ \colv{n_k+1}{2}
[/tex]

Homework Equations

The Attempt at a Solution

I applied pascals identity to remove "+ 1", and now I have the formula:
[tex]
\newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}
\colv{n}{2} < \colv{n_1}{2} + \colv{n_2}{2} + ... + \colv{n_k}{2}
[/tex]

But I must admit that this still doesn't seem to help my understanding of how to attack this problem.

 

[lanedance]

have you tried writing out the LHS explicitly as
[tex]\newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)} \colv{n_k}{2} = \frac{n_k(n_k -1)}{2}[/tex]

I haven't followed it though, but could be good place to start. Trying the 2 var case say n = p+q could also lead to some useful insights

 

[pazo]

I made an error. Sorry!
[tex]
\newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}
\colv{n+1}{2} > \colv{n_1+1}{2} + \colv{n_2+1}{2} + ...+ \colv{n_k+1}{2}
[/tex]
is the right one(I changed < with >).

 

[lanedance]

ok so have you tried the other stuff yet?

 

[pazo]

lanedance:

I tried, but didn't get any further. I need, somehow, to get the part in where [tex]2 \leq k \leq n[/tex]. But then again if k = n it won't be true. So I also need the part where

[tex]
\sum_{i=1}^k n_i = n
[/tex]

Do you have any advice on how to do that? Or am I completely wrong? :)

 

[lanedance]

well if k = n then, ni = 1, and the inequality becomes

[tex]\newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}\colv{n+1}{2} > \colv{2}{2} + \colv{2}{2} + ...+ \colv{2}{2} = 1+1+..+1 = n[/tex]

[tex]\newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}\colv{n+1}{2} = \frac{(n+1)!}{(n-1)!(2)!} = \frac{(n+1)n}{2} > n[/tex]

so the inequality is true as n >= 2

 

[lanedance]

now see what you can do with post #2