Combination to find integers satisfying a condition

Question

Let $n$ and $k$ be positive integers such that $n\ge\frac{k(k+1)}{2}$. The number of solutions $(x_1,x_2,\dots,x_{k})$, with $x_1\ge1$, $x_2\ge2$,..., $x_{k}\ge k$ for all integers satisfying $x_1+x_2+\dots+x_{k}=n$ is?

I substituted the last equation in the first inequality. $$x_1+x_2+\dots+x_{k}\ge\frac{k(k+1)}{2}.$$ Took $x_1$ as $1+ t_1$, $x_2$ as $2+t_2$...where $t_i\ge 0$. On simplifying by using sum of k numbers, I end with with $t_1+t_2+\dots+t_{k} \ge0$. Since $x_1,x_2$... are in increasing order, and sum of all $t$ values is $0$, I conclude that this is only possible when $t=0$. Therefore only one solution is possible when $LHS = RHS$. The inequality is not valid.

But the answer is $\frac{1}{2}(2n-k^2+k-2)$. What am I missing here?

Answer 1

No, the sequence $x_1,x_2,\dots,x_{k}$ is not necessarily increasing, so your conclusion is not correct.

Let $t_k=x_k-k\geq 0$, then we have to count the number of non-negative integer solutions of $$t_1+t_2+\dots+t_k=n-\frac{k(k+1)}{2}$$ which is, by Stars-and-Bars, given by $$\binom{n-\frac{k(k+1)}{2}+k-1}{k-1}=\binom{\frac{2n-k^2+k-2}{2}}{k-1}.$$

P.S. My answer is correct. Probably there is a typo in your book. The integer $\binom{\frac{2n-k^2+k-2}{2}}{k-1}$ is precisely the coefficient of $t^n$ in $$ (t + t^2 +t^3+ \dots)(t^2 + t^3 +t^4+\dots)\dots (t^k + t^{k+1}+t^{k+2}+\dots),$$ that is $$[t^n]\prod_{j=1}^k\frac{t^j}{1-t}=[t^{n-\frac{k(k+1)}{2}}](1-t)^{-k} =(-1)^{{n-\frac{k(k+1)}{2}}}\binom{-k}{n-\frac{k(k+1)}{2}}=\binom{n-\frac{k(k+1)}{2}+k-1}{k-1}.$$ Numerical example. Take $n=8$ and $k=3$, then it is easy to see that $$ (t + t^2 +t^3+ \dots)(t^2 + t^3+ t^4 +\dots)(t^3 + t^{4}+t^{5}+\dots) =t^6+3t^7+6t^8+\dots$$ and the coefficient of $t^8$ is $6$: $$\binom{\frac{16-9+3-2}{2}}{3-1}=\binom{4}{2}=6.$$