# Count the number of integer solutions

1. Nov 17, 2005

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

Last edited: Nov 17, 2005
2. Nov 17, 2005

### 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 |x1| > 0, then x1 has two possible values whereas when |x1| = 0 then x1 = 0 only. It's a start.