# Non-negative integer solutions to $2a+b\leq n$.

I am trying to find number of solutions to $2a+b\leq n$ for $a,b\geq 0$ given some $n\geq 0$.

Anyone have ideas? Maybe stars and bars? Thank you!

Generating function approach

It's the $n$th coefficient of the expansion of $$\frac{1}{(1-x)^2}\cdot \frac{1}{1-x^2}\tag{1}$$

Multiplying numerator and denominator by $(1+x)^2$ and you get:

$$\frac{(1+x)^2}{(1-x^2)^3} = (1+x)^2\sum_{k=0}^{\infty}\binom{k+2}{2}x^{2k}$$

So if $n=2m$ is even, then the coefficient of $x^{n}$ is $\binom{m+2}{2}+\binom{m}{2}$, and if $n=2m+1$ is odd, then the coefficient of $x^n$ is $2\binom{m+2}{2}$.

This can be written as: $$\left\lfloor \frac{(n+2)^2}{4}\right\rfloor$$

Or:

$$\frac{2n^2+8n+7}{8}+\frac{(-1)^n}{8}\tag{2}$$

You could also get this formula by doing partial fractions to write (1) as:

$$\frac{a}{(1-x)^3}+\frac{b}{(1-x)^2}+\frac{c}{1-x}+\frac{d}{1+x}$$

and then get the formula $a\binom{n+2}{2}+b\binom{n+1}{1}+c+d(-1)^n$.

Wolfram Alpha gives me $a=1/2,b=1/4,c=1/8,d=1/8$.

Formula (2) indicates a recursion:

$$a_{n+4}=2a_{n+3}-2a_{n+1}+a_n$$

Not sure if you can find a nice counting argument for that recursion.

• Makes sense to me. Thank you! – Ryan Stodola Jan 16 '17 at 20:51

$a$ can be anything be anything between $0$ and $\lfloor n/2 \rfloor$ (inclusive;) and $b$ can be anything from $0$ to $n - 2a$.

So there are $\sum_{a=0}^{\lfloor n/2 \rfloor}\sum_{b= 0}^{n-2a}1$ solutions.

$\sum_{a=0}^{\lfloor n/2 \rfloor}\sum_{b= 0}^{n-2a}1=$

$\sum_{a=0}^{\lfloor n/2 \rfloor}(n - 2a + 1)=$

$(\lfloor n/2 \rfloor + 1)n + (\lfloor n/2 \rfloor + 1) - 2\sum_{a=0}^{\lfloor n/2 \rfloor}a=$

$(\lfloor n/2 \rfloor + 1)n + (\lfloor n/2 \rfloor + 1) -2\frac{\lfloor n/2 \rfloor (\lfloor n/2 \rfloor + 1)}2=$

$(\lfloor n/2 \rfloor + 1)(n - \lfloor n/2 \rfloor + 1)=$

$(\lfloor n/2 \rfloor + 1)(\lceil n/2 \rceil + 1)$

If $n$ is even this is $(n/2 + 1)^2$.

If $n$ is odd this is $(n/2 + 1/2)(n/2 + 1/2 + 1) = \frac{(n + 1)(n+3)}4$.

• You use $k$ when I think you mean $a$, and it should start at $a=0$. And $b$ can be anything from $0$ to $n-2a$. So it should be $$\sum_{a=0}^{\lfloor n/2\rfloor} (n-2a+1)=(n+1)(\lfloor n/2\rfloor+1)-\lfloor n/2\rfloor(\lfloor n/2\rfloor +1)=(\lfloor n/2\rfloor+1)(\lceil n/2\rceil +1)$$ – Thomas Andrews Jan 17 '17 at 14:36
• Oh, I thought (probably incorrectly) that b and a had to be positive. and I did mean a. Well, actually I meant k and I meant to replace the a with a k because .... I was typing in a hurry and I was thinking of a as fixed and k can be the variables to represent the different fixed values of a.... Moral: Don't do math when your favorite tv show is just about to start. – fleablood Jan 17 '17 at 16:42
• Um why $\sum (n-2a +1)$ rather than $\sum (n-2a)$? – fleablood Jan 17 '17 at 16:58
• Because the number of values $b$ with $0\leq b\leq m$ is $m+1$. Same mistake - $b$ is allowed to be $0$. @fleablood – Thomas Andrews Jan 17 '17 at 17:13
• b is allowed to be 0 (if n is even) but b = n-2a; not b = n-2a +1 and .... argh! – fleablood Jan 17 '17 at 17:36