5
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Could you please check the given answer? In my opinion is the one given in my answer below. $\endgroup$ – Robert Z Jul 25 '20 at 14:38
  • $\begingroup$ @RobertZ hey i just saw the answer as my net was down. the answer given is 1/2 (2n-(k^2)+k-2) and the answer you have given doesn't simplify to it. The method given in the book uses the sum of coefficients of t^n in (t + t^2 +t^3 ...)(t^2 + t^3 +....)(t^k + t^(k-1)+...). If this is helpful in answering as i didnt understand what happening here. $\endgroup$ – Shaurya Goyal Jul 30 '20 at 13:00
  • $\begingroup$ What is the title of the book? $\endgroup$ – Robert Z Jul 30 '20 at 13:11
  • $\begingroup$ it is a book of past IIT-JEE questions $\endgroup$ – Shaurya Goyal Jul 30 '20 at 13:12
  • $\begingroup$ I edited my answer (which is correct). Please take a look at the P.S. $\endgroup$ – Robert Z Jul 30 '20 at 13:51
2
$\begingroup$

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.$$

$\endgroup$
2
  • $\begingroup$ doesn't this x1≥1, x2≥2,..., xk≥k imply it is increasing ? x1+x2+⋯+xk=n and n and k both are positive. sum we know xk≥1 as the first lowest number x1≥1 $\endgroup$ – Shaurya Goyal Jul 31 '20 at 12:59
  • $\begingroup$ No. Take $n=12$ and $k=3$, then $x_1=5\geq 1$, $x_2=4\geq 2$ and $x_3=3\geq 2$ satisfy the given conditions, but they are not increasing. $\endgroup$ – Robert Z Jul 31 '20 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.