1
$\begingroup$

I'm having a huge problem even understanding what to do here. Any guidance to get me going would be greatly appreciated.

If $n,k$ are positive integers, how many integral solutions are there to the equation $$ x_1+x_2+ \cdots +x_k=n $$ if for all $i$, $x_i\geq2i$.

I've tried creating the equations for n=1 and on up, but that's not providing me any answers or patterns. Any help would be greatly appreciated. I think I need to create a weight function somehow, but even then I'm lost. Thank you.

$\endgroup$
1
$\begingroup$

Hint: We want to find the number of non-negative solutions of $$y_1+y_2+\cdots +y_k=n-2(1+2+\cdots+k).\tag{1}$$

For any non-negative integer solution of Rquation (1), if we then set $x_i=y_i+2i$, we obtain a solution of your constrained problem. And any solution of the constrained problem produces a solution of Equation (1).

Remark: The arithmetic may be a little nicer if we find the number of solutions of $z_1+z_2+\cdots+z_k =n-(1+3+5+\cdots +(2k-1))$ is positive integers.

$\endgroup$
  • $\begingroup$ Thank you! That was incredibly helpful. I took that and broke it down into a different problem from one of my different classes. $\endgroup$ – Ambi0521 Nov 19 '13 at 20:34
  • $\begingroup$ You are welcome. I left the "Stars and Bars" part (number of non-negative, or alternately number of positive) solutions of $w_1+\cdots+w_k=m$ to you, on the assumption that it is familiar. You could also go directly to generating functions without the preliminary reduction. But reduction to a familiar problem seems like the best way to go. $\endgroup$ – André Nicolas Nov 19 '13 at 20:42

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.