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

Question

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!

Answer 1

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.

Answer 2

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