Count the number of integer solutions

[benorin]

Count the number of integer solutions of (rather, # of integer lattice points such that)

$$n+\sum_{k=1}^{n} \left| x_{k}\right| \leq N$$

Not homework, so no rush. I have worked it through before with a prof., but he's so brilliant I didn't understand much of anything he said . His solution involed a generating function, something like the coefficient of the blah term in the expansion of blahblah.

Note that the LHS is the height of a polynomial with integer coefficients, although it has nothing to do with the solution.

 

[AKG]

If n > N, the answer is 0. Otherwise, the problem reduces to finding the lattice point solutions of:

$$\sum _{k=1} ^n |x_k| \leq N'$$

where N' > 0. Let f(N',n) denote the number of solutions. Then we want to find f(N',n) and this is just:

$$f(N',n) = f(N',n-1) + 2\sum _{k=1} ^{N'} f(N'-k,n-1)$$

We get this because $\sum _{k=1} ^n |x_k| = |x_1| + \sum_{k=2} ^n |x_k|$ and when |x₁| > 0, then x₁ has two possible values whereas when |x₁| = 0 then x₁ = 0 only. It's a start.