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 \leq k \leq n, and \sum_{i=1}^k n_i = n the following is true
<br /> \newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}<br /> \colv{n+1}{2} &lt; \colv{n_1+1}{2} + \colv{n_2+1}{2} + ...+ \colv{n_k+1}{2}<br />

Homework Equations

The Attempt at a Solution

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

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
\newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)} \colv{n_k}{2} = \frac{n_k(n_k -1)}{2}

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!
<br /> \newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}<br /> \colv{n+1}{2} &gt; \colv{n_1+1}{2} + \colv{n_2+1}{2} + ...+ \colv{n_k+1}{2}<br />
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 2 \leq k \leq n. But then again if k = n it won't be true. So I also need the part where

<br /> \sum_{i=1}^k n_i = n <br />

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

\newcommand{\colv}[2] {\left(\begin{array}{c} #1 \\ #2 \end{array}\right)}\colv{n+1}{2} &gt; \colv{2}{2} + \colv{2}{2} + ...+ \colv{2}{2} = 1+1+..+1 = n

\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} &gt; n

so the inequality is true as n >= 2

 

[lanedance]

now see what you can do with post #2