- #1
henpen
- 50
- 0
Question:
Given a non-negative integer N, show many sets of non-negative integers [itex] (a,b,c,d) [/itex] satisfy [itex] 2a+b+c+d=N [/itex]
Proposed (and roadblocked) solution:
Case 1: [itex]2a=0[/itex]
Then there are [tex]\binom{N+2}{2}[/tex] solutions (easy to prove).
Case 2: [itex]2a=2[/itex]
Then there are [tex]\binom{N+2-2}{2}[/tex] solutions.
Case 3: [itex]2a=4[/itex]
Then there are [tex]\binom{N+2-4}{2}[/tex] solutions.
...
Thus the answer should be [tex]\large \sum_{i=0}^{i=1+ \left \lfloor \frac{N}{2} \right \rfloor}\binom{N+2-2i}{2}[/tex]
The answer I'm looking for is actually [itex]2^{N+1}-1[/itex], and numerically my method doesn't check. Where have I gone wrong? I'm fairly confident my analysis for each case 1 was correct.
Given a non-negative integer N, show many sets of non-negative integers [itex] (a,b,c,d) [/itex] satisfy [itex] 2a+b+c+d=N [/itex]
Proposed (and roadblocked) solution:
Case 1: [itex]2a=0[/itex]
Then there are [tex]\binom{N+2}{2}[/tex] solutions (easy to prove).
Case 2: [itex]2a=2[/itex]
Then there are [tex]\binom{N+2-2}{2}[/tex] solutions.
Case 3: [itex]2a=4[/itex]
Then there are [tex]\binom{N+2-4}{2}[/tex] solutions.
...
Thus the answer should be [tex]\large \sum_{i=0}^{i=1+ \left \lfloor \frac{N}{2} \right \rfloor}\binom{N+2-2i}{2}[/tex]
The answer I'm looking for is actually [itex]2^{N+1}-1[/itex], and numerically my method doesn't check. Where have I gone wrong? I'm fairly confident my analysis for each case 1 was correct.