Integer sum combinatorics problem

[henpen]

Question:
Given a non-negative integer N, show many sets of non-negative integers $(a,b,c,d)$ satisfy $2a+b+c+d=N$

Proposed (and roadblocked) solution:

Case 1: $2a=0$
Then there are $$\binom{N+2}{2}$$ solutions (easy to prove).

Case 2: $2a=2$
Then there are $$\binom{N+2-2}{2}$$ solutions.

Case 3: $2a=4$
Then there are $$\binom{N+2-4}{2}$$ solutions.
...

Thus the answer should be $$\large \sum_{i=0}^{i=1+ \left \lfloor \frac{N}{2} \right \rfloor}\binom{N+2-2i}{2}$$

The answer I'm looking for is actually $2^{N+1}-1$, and numerically my method doesn't check. Where have I gone wrong? I'm fairly confident my analysis for each case 1 was correct.

 

[awkward]

$2^{N+1}-1$?

I count 13 solutions when N=3.

0 0 0 3
0 0 1 2
0 0 2 1
0 0 3 0
0 1 0 2
0 1 1 1
0 1 2 0
0 2 0 1
0 2 1 0
0 3 0 0
1 0 0 1
1 0 1 0
1 1 0 0

 

[henpen]

My formula would agree with you.
Perhaps the question is incorrect (Original source- near bottom of page)

 

[awkward]

Starting with N=1, the values I get are 3, 7, 13, 22, 34, 50. I haven't checked your answer against these values-- I'll leave that up to you-- but it appears the answer given on the page you linked to is incorrect.

 

[henpen]

Starting with N=1, the values I get are 3, 7, 13, 22, 34, 50. I haven't checked your answer against these values-- I'll leave that up to you-- but it appears the answer given on the page you linked to is incorrect.

My formula agrees for those cases. Thanks for the help.

 

[Bacle2]

Maybe you're looking for the number of solutions to :

x₁+x₂+...+x_k=n

for x_i, n ≥ 0 , it is :

(n+k-1)C(k-1) , where aCb is "a choose b"

If you want all x_i>0 , the number of solutions is (n-1)C(k-1)

( throw one ball in each box and then apply the first method)