Question

A) How many ordered sets of non-negative integers \((x, y)\) are there such that

\(x+y \le 20\)

?

B) generalize the result to \(x+y \le n\)

Answer 1

I think A) is 21 and B) is n+1. Don't count on me though.

Answer 2

thats right if it is equality : x+y = 20

Answer 3

I have a idea! We can use recurrence relations to find this out.
Let \(N(eq)\) be the function that returns the number of ordered set that satisfies the equation \(eq\).
For \(n=0\), \(N(x+y\leq0)=1\)
For \(n=1\), \(N(x+y\leq1)=3=N(x+y\leq0)+N(x+y=1)\)
For \(n=2\), \(N(x+y\leq2)=N(x+y\leq1)+N(x+y=2)\)

Did I do something wrong?

Answer 4

looks perfect to me ! you want to iterate n=0..20 is it ?

Answer 5

F(n) = F(n) + F(n-1)

Answer 6

Ah. Let \(E(n)=N(x+y=n)\).
\(E(n)=n+1\).
\[
\begin{align*}
N(x+y\leq n)&=\sum_{k=0}^nE(k)\\
&=\sum_{k=0}^n(k+1)\\
&=\frac{n(n+1)}{2}+n+1\\
&=\frac{(n+1)(n+2)}{2}
\end{align*}
\]

Answer 7

Exactly ! that expression looks pretty xD

n=0 : (0+1)
n=1 : (1+1)
n=2 : (2+1)
...
n=n : (n+1)
-------------
n(n+1)/2 + (n+1)

Answer 8

i think this should work :

Number of non-negative integer solutions for \(x+y \le n\) is\[\large \binom{n+1}{2}\]

Answer 9

may be we can go ahead and generaluze this to \(\large ax+by \le n\) xD not sure whether it would be easy..

Answer 10

Have to get my dinner now. Chat later.