Prove that the number of answers for $|a_1|+|a_2|+...+|a_k| \le n$ is equal to the number of answers for $|a_1|+|a_2|+...+|a_n| \le k$.

Question

I'm trying to solve this problem:

Prove that the number of answers for $|a_1|+|a_2|+...+|a_k|≤n$ is equal to the number of answers for $|a_1|+|a_2|+...+|a_n|≤k$. all $a_i$ is an integer number.

I have a solution for non negative $a_i$: We convert $|a_1|+|a_2|+...+|a_k|≤n$ to $a_1+a_2+...+a_k+c=n$ and convert $|a_1|+|a_2|+...+|a_n|≤k$ to $a_1+a_2+...+a_n+c=k$.

By bars and stars theorem: Number of answers for $a_1+a_2+...+a_k+c=n$ is equal to $\binom{n+k}{k}$ and number of answers for $a_1+a_2+...+a_n+c=k$ is equal to $\binom{n+k}{n}$. That $\binom{n+k}{k} = \binom{n+k}{n}$.

but i don't know how to prove for negative integers.

Answer 1

Let $f(n,k)$ be the number of solutions to $|a_1|+\dots+|a_n|\le k$. Note that $$ f(n,k) = f(n-1,k)+2f(n-1,k-1)+2f(n-1,k-2)+\dots+2f(n-1,0),\tag{*} $$ by conditioning on the value of $a_n$. Rearranging, and using $(*)$ applied to $f(n,k-1)$, we get $$ \begin{align} f(n,k) &= f(n-1,k)+f(n-1,k-1)+[f(n-1,k-1)+2f(n-1,k-2)+\dots+2f(n-1,0)]\\ &= f(n-1,k)+f(n-1,k-1)+f(n,k-1) \end{align} $$ The above shows that $f(n,k)$ obeys a recurrence which is symmetric in $n,k$. Since you can easily verify the symmetric base cases $f(n,0)=f(0,k)=1$, the result $f(n,k)=f(k,n)$ follows by induction.

Answer 2

We count the number of solutions to $\sum_{i=1}^n |a_i|\leq k$.

There will be $j\leq r:={\rm min}\{n,k\}$ of the $a_i$ that are $\ne0$, call them $a_{i_1}$, $\ldots$, $a_{i_j}$. The $i_l$ $(1\leq l\leq j)$ can be chosen in ${n\choose j}$ ways. For the chosen $i_l$ put $|a_{i_l}|=x_l+1$ with $x_l\geq 0$. Then we have to count the number of solutions to $x_1+\ldots+x_j+c=k-j$. This number is ${k\choose j}$. It has to be multiplied by $2^j$ in order to account for the choice of the signs of the corresponding $a_{i_l}$. The total number of solutions therefore comes to $$\sum_{j=0}^r{n\choose j}{k\choose j}2^j\ ,$$ which is symmetric in $n$ and $k$.

Answer 3

Introducing notation $A_i=|a_i|$ the first of inequalities can be rewritten as: $$ A_1+A_2+...+A_k\le n.\tag1 $$ Any solution to $(1)$ can be viewed as composed of $i$ zeros ($0\le i\le k$) and $k-i$ non-zeros. Each non-zero value doubles the number of solutions to original equation (which can be both positive and negative). The overall number of solutions is therefore $$ \sum_{i=0}^{k}\binom{k}{i}\binom{n}{k-i}2^{k-i} \stackrel{i=k-j}=\sum_{j=0}^{k}\binom{k}{j}\binom{n}{j}2^{j} =\sum_{j=0}^{\min(k,n)}\binom{k}{j}\binom{n}{j}2^{j},\tag2 $$ where $\binom{k}{i}$ counts the number of ways to place $i$ zeros into $k$ cells, and $\binom{n}{k-i}$ counts the number of positive solutions to the inequality $$ p_1+p_2+\cdots+p_{k-i}\le n. $$

In view of symmetry of $(2)$ with respect to interchange of $n$ and $k$ the original statement is proved.

Answer 4

Just to show another approach to the answer already given by C.Blatter, let's start and consider $$ \left\{ \matrix{ 0 \le b_{\,j} \in \mathbb Z \hfill \cr b_{\,1} + b_2 + b_{\,3} + \cdots + b_{\,k} \le n \hfill \cr} \right. $$ Then the number of solutions is the integral volume $V(k,n)$ of k-D simplex, with edge segments $(0,n)$, thus of length $n+1$.
It is not difficult to demonstrate that $$V(k,n)= \binom{n+k}{n}= \binom{n+k}{k}=V(n,k)$$ then the hypothesis is already true in this case.

We can then partition the above solutions into those that contains $j$ variables null and the remaining $k-j$ having values greater than $0$. We can assign the null variables in $\binom{k}{j}$ ways.
That corresponds to $$ V(k,n)= \binom{n+k}{n}= \binom{n+k}{k} = \sum\limits_{0\, \le \,j\, \le \,k} { \binom{n}{k-j} \binom{k}{j} } $$

Coming to our present case, for each non null variable $b_j$ we can assign two values to the corresponding $a_j$, and just one to the null variables. So in this case the volume will be $$ V_{\,a} \,(k,n) = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,k} \right)} {\binom{n}{k-j} \binom{k}{j} 2^{\,k - j} } = \sum\limits_{\left( {0\, \le } \right)\,l\,\left( { \le \,k} \right)} {\binom{n}{l} \binom{k}{l} 2^l } = V_{\,a} \,(n,k) $$

Therefore the hypothesis is demonstrated.

Answer 5

I just saw this question as it came back to the front page. I wrote this answer a couple of months ago, which proves that this number is $$ \sum_{k=0}^n2^k\binom{n}{k}\binom{m}{k} $$ which is also shown in answers to this question. My answer starts with a recurrence (like Mike Earnest's answer) and solves it by induction.