Maths Olympiad Prep

Library / /437 of 520

Combinatorics Difficulty 4.5 AIME Prove it

Let P(n,m)=k=0n(1)k(nk)mm+kP(n, m) = \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\frac{m}{m+k} and Q(n,m)=(n+mm)Q(n, m) = \binom{n+m}{m}, where m,nNm,n\in\mathbb{N}^*.
1. When m=1m=1, find the values of P(n,1)P(n, 1) and Q(n,1)Q(n, 1).
2. For all mNm\in\mathbb{N}^*, prove that P(n,m)Q(n,m)P(n, m)\cdot Q(n, m) is constant.

Solution

1. Given that P(n,m)=k=0n(1)k(nk)mm+kP(n, m) = \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\frac{m}{m+k} and Q(n,m)=(n+mm)Q(n, m) = \binom{n+m}{m}, and m,nNm,n\in\mathbb{N}^*; when m=1m=1,

P(n,1)=k=0n(1)k(nk)11+kP(n, 1) = \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\frac{1}{1+k} can be rewritten using the identity (n+1k+1)=(nk)+(nk+1)\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}, which simplifies to 1n+1\frac{1}{n+1}.

Q(n,1)=(n+11)=n+1Q(n, 1) = \binom{n+1}{1} = n+1.

Therefore, P(n,1)Q(n,1)=1P(n,1)\cdot Q(n,1) = \boxed{1}.

2. Let's prove that P(n,m)Q(n,m)P(n, m)\cdot Q(n, m) is a constant for all mNm \in \mathbb{N}^*.

Starting with P(n,m)=k=0n(1)k(nk)mm+kP(n, m) = \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\frac{m}{m+k}, which can be decomposed into two parts:

P(n,m)=1k=1n1(1)k((n1k)+(n1k1))mm+k+(1)nmm+nP(n, m) = 1 - \sum_{k=1}^{n-1}(-1)^{k}\left(\binom{n-1}{k} + \binom{n-1}{k-1}\right)\frac{m}{m+k} + (-1)^{n}\frac{m}{m+n}.

The first summation telescopes and using the identity (nk)=(n1k)+(n1k1)\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}, we get:

P(n,m)=P(n1,m)+mn[k=1n(1)k(nk)(1mm+k)]P(n, m) = P(n-1, m) + \frac{m}{n}\left[\sum_{k=1}^{n}(-1)^{k}\binom{n}{k}\left(1 - \frac{m}{m+k}\right)\right].

Simplifying further by distributing the summation and collecting terms:

P(n,m)=P(n1,m)+mn[1k=1n(1)k(nk)mm+k]P(n, m) = P(n-1, m) + \frac{m}{n}\left[-1 - \sum_{k=1}^{n}(-1)^{k}\binom{n}{k}\frac{m}{m+k}\right].

Hence, we obtain a recursive relationship:

P(n,m)=P(n1,m)mnP(n,m)P(n, m) = P(n-1, m) - \frac{m}{n} P(n, m).

From the recursion, we can infer that:

P(n,m)=n!m!(n+m)!P(0,m)=1(n+mn)P(n, m) = \frac{n! \cdot m!}{(n+m)!} P(0, m) = \frac{1}{\binom{n+m}{n}}.

Since Q(n,m)=(n+mn)Q(n, m) = \binom{n+m}{n}, we find that:

P(n,m)Q(n,m)=1P(n, m) \cdot Q(n, m) = \boxed{1}, demonstrating that it is indeed a constant value.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.