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
$$\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}$$

Homework Equations

The Attempt at a Solution

I applied pascals identity to remove "+ 1", and now I have the formula:
$$\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}$$

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!
$$\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}$$
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

$$\sum_{i=1}^k n_i = n$$

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} > \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} > n$$

so the inequality is true as n >= 2

 

[lanedance]

now see what you can do with post #2