Mad Binomial Sum

Okay time for the combinatorial solution:

Consider the number ways we can choose a committee of k people and nominate two people to be president and chairperson (who are permitted to be the same person). This is just $f(n)$ .

Now we count it a different way, which is choosing the president and chairperson first and then choosing the rest of the group. When the chairperson and president are the same we have $n2^{n-1}$ choices as there are $n$ choices for the president/chairperson, and every other person can either be in the group or not. When the chairperson and president are not the same we have $n(n-1)2^{n-2}$ ways of choosing the committee, by a simple count. Adding these together gets $n^2 2^{n-2}+n2^{n-2}$ .

Now we just sub in $n=2016$ and get $f(2016) = 2016 \cdot 2017 \cdot 2^{2014}$ so the answer is $2016+2014=\fbox{4030}$ .

$\large (x+1)^n= C^{n}_{0}+C^{n}_{1}x+C^{n}_{2}x^2+C^{n}_{3}x^3+\dots+C^{n}_{n-1}x^{n-1}+C^{n}_{n}x^n$

Differentiate both sides $w. r. t. x$ :

$\large n(x+1)^{n-1}= C^{n}_{1}+2C^{n}_{2}x+3C^{n}_{3}x^2+\dots+(n-1)C^{n}_{n-1}x^{n-2}+nC^{n}_{n}x^{n-1}$

Multiply both sides with $x$ :

$\large nx(x+1)^{n-1}= C^{n}_{1}x+2C^{n}_{2}x^2+3C^{n}_{3}x^3+\dots+(n-1)C^{n}_{n-1}x^{n-1}+nC^{n}_{n}x^{n}$

Differentiate both sides $w. r. t. x$ :

$n(x(n-1)(x+1)^{n-2}+(x+1)^{n-1})= C^{n}_{1}+2^2C^{n}_{2}x+3^2C^{n}_{3}x^2+\dots+(n-1)^2C^{n}_{n-1}x^{n-2}+n^2C^{n}_{n}x^{n-1}$

Put $x=1$ :

$n((n-1)(2)^{n-2}+(2)^{n-1})= C^{n}_{1}+2^2C^{n}_{2}+3^2C^{n}_{3}+\dots+(n-1)^2C^{n}_{n-1}+n^2C^{n}_{n}=f(n)$

$\large \Rightarrow f(2016)=2016((2015)2^{2014}+2^{2015}) = 2016 \cdot 2017 \cdot 2^{2014}$

$\large \Rightarrow A = 2016, B = 2014$

$\large A+B =2016+2014=4030$ .

Note that $\frac{\dbinom nm}{\dbinom {n-1}{m-1}}=\frac{n}{m}$ and $\displaystyle \sum^{n}_{m=0}\dbinom nm =2^n$ .

$\displaystyle \sum^{n}_{m=1}m^2 \dbinom nm =n \displaystyle \sum^{n}_{m=1}(m-1+1) \dbinom {n-1}{m-1} \\ n\left\{ \displaystyle \sum^{n}_{m=1} (m-1) \dbinom {n-1}{m-1}+\displaystyle \sum^{n}_{m=1} \dbinom {n-1}{m-1} \right\} \\ n \left\{ (n-1) \displaystyle \sum^{n}_{m=2} \dbinom {n-2}{m-2}+2^{n-1}\right\} \\ n \left\{ (n-1)2^{n-2}+2^{n-1} \right\}=n(n+1)2^{n-2}$

I will prove that $\displaystyle f(n) = \sum_{m=1}^n m^2 \dbinom nm = n(n+1) 2^{n-2}$ by applying the binomial identity $\displaystyle \sum_{j=0}^k \dbinom kj = 2^k$ repeatedly.

$\begin{aligned} f(n) &=& \sum_{m=1}^n m^2 \dbinom nm = 1^2 \dbinom n1 + \sum_{m=2}^n m^2 \dbinom nm \\ &=& n + \sum_{m=2}^n [ m(m-1) + m ] \dbinom nm \\ &=& n + \underbrace{\sum_{m=2}^n \left [ m(m-1) \dbinom nm \right ]}_{:= I} + \underbrace{\sum_{m=2}^n \left [ m \dbinom nm \right ]}_{:= J} \\ \end{aligned}$

Let's solve for $I$ and $J$ separately.

For $m\geq 2$ , $\begin{aligned} m(n-1) \dbinom nm &=& m(m-1) \dfrac{n!}{(n-m)!m!} = \cancel{m(m-1)} \dfrac{n!}{(n-m)!\cancel{m(m-1)} (m-2)!} \\ & = &\dfrac{n!}{(n-m)!(m-2)!} = n(n-1) \dbinom {n-2}{m-2} \; . \end{aligned}$

Similarly, for $m \geq 1$ , $m \dbinom nm = n\dbinom {n-1}{m-1}$ .

Hence, $\displaystyle I = n(n-1) \sum_{m=2}^n \dbinom{n-2}{m-2} = n(n-1) 2^{n-2}$ and $\displaystyle J = n \sum_{m=2}^n \dbinom{n-1}{m-1} = n (2^{n-1} - 1)$ .

By substituting them into $f(n)$ and simplify, we will obtain the desired result $\displaystyle f(n) = \sum_{m=1}^n m^2 \dbinom nm = n(n+1) 2^{n-2}$ .

With $f(2016) = 2016 \times 2017 \times 2^{2014}$ , our answer is $A+B = 2016 + 2014 = \boxed{4030}$ .

---

Food for thought: Can we solve this via induction ? If yes, is it easier or harder to solve via induction?

I will be using s(m=1, n): instead of the epsilon and b(n, m) instead of the regular binomial notation both because I am too lazy to actually learn how to write proper notation here. Anyways, we have f(n)=s(m=1, n):m m n!/((m)! (n-m)!)=s(m=1, n):m n!/((m-1)! (n-m)!)=s(m=1, n):n m (n-1)!/((m-1)!(n-m)!)=n (s(m=1, n):m b(n-1, m-1)) the trick is recognising that for every iteration, we are just starting a new series b(n-1, m-1) without the previous terms as increasing m is the same as simply adding a new copy of the binomial coefficient in the sum, a full binomial series will equate to 2^(n-1) by 2^a=(1+1)^a=s(j=0, a):b(a, j) so we have (taking into account the terms not included in each new case of the series in the sum) f(n)=n ((s(m=1, n):2^(n-1))-(s(m=1, n-1):s(h=0, m):b(n-1, h))) we will then take into account that summing something again n times is the same as multiplying it by n, and the fact that the second part of the thing being multiplied by n is (n-1) 2^(n-1)/2 as we can always pair the ath last element with the ath first element in the series to produce 2^(n-1) meaning the average is 2^(n-1)/2 for the terms in the series (except for the middle term if there is one, but that will always be the equivalent to (n-1) 2^(n-1)/2 anyways), this is caused by the symmetry of the binomial series (I will leave the meet to you), and there are n-1 terms, we will also be taking into account the fact that 2 2^(n-2)=2^(n-1). Anyways, we can now finally discover the equation f(n)=n (2 n 2^(n-2)-(n-1) 2^(n-2))=n (2 n-n+1) 2^(n-2)=n (n+1) 2^(n-2) so B=n-2, A=n, and hence A+B=n-2+n=2 n-2 and since n=2016, the answer is 2 2016-2=4032-2=4030. I probably made a ridiculous number of grammatical mistakes and I was probably way too vague, but you should be able to get the point if you can read through this onslaught of text.