# Counting number of pairs whose sum is less than k

261 views

How many pairs $(x,y)$ such that $x+y <= k$, where x y and k are integers and $x,y>=0, k > 0$.

1. Solve by summation rules.
2. Solve by combinatorial argument.

1 vote
It is similar to saying that we have to put n identical balls in two different boxes(the two boxes being x and y). This can be done in (k+1)!/(k!*1!) ways if x>=0 and y>=0.(How? see at end of  answer). In ques, we have to put i balls( such that 1<=i<=k) in two boxes. This can be done in  $\sum_{i=1}^{k}$ $\left \{ (i+1)!/(i!*1!)\right \}$

----------------------------------------------------------------------------------------------

Number of ways of putting n identical balls in p boxes such that boxes can be empty(obviously not all boxes can be empty):

Put the n balls linearly. Draw p-1  lines to divide this linear arrangement of balls in p partitions. Now we have to arrange n+(p-1) things such that n are of same kind and p-1 are of same kind. This can be done in (n+p-1)!/(n!*(p-1)!).

## Related questions

1
687 views
Use the patterns given to prove that $\sum\limits_{i=0}^{n-1} (2i+1) = n^2$ (You are not permitted to employ induction) Use the result obtained in (a) to prove that $\sum\limits_{i=1}^{n} i = \frac{n(n+1)}{2}$
My Question $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ I have to check that it is Turing Recognizable or not (i.e R.E) My Approach/Doubt Question taken from https://gateoverflow.in/7427/which-following ... $100$ $T_{yes}\subset T_{no}$. Hence it is not RE.But in the solution it is R.E.
Prove the identity: \begin{align*} &\sum_{i=0}^{n}\sum_{j=0}^{i} a_ia_j = \frac{1}{2}\left ( \left ( \sum_{i=0}^{n}a_i \right )^2 + \left ( \sum_{i=0}^{n}a_i^2 \right )\right ) \end{align*}