Voofie | Repeated sum and partial difference equation

Content

1 Introduction
2 The Problem
3 A Standard Solution
4 Recurrence Approach
5 Partial Difference Equation
6 Generating Function
7 Other Summation Function
8 Conclusion

Introduction

In this article, I will first state the problem that I would like to solve. Then I will give the standard solution using the line and bar counting method. Next, I will transform it into a partial difference equation, which can help us to simplify the following repeated sum:

$\f[\sum _{n_1=0}^n \sum _{n_2=0}^{n_1} \sum _{n_3=0}^{n_2} \text{...}\sum _{n_{k}=0}^{n_{k-1}}a_{n_{k}}\f]$

For any $\f$a_k\f$$ .

The Problem

Find the number of solutions to the following equation with non-negative integral solution:

$\f[x_1+x_2+\text{...}+x_k=n\f]$

A Standard Solution

For illustration, we fixed k = 4, n = 6.

We may think of, we are putting 6 balls into 4 boxes. And how many ways we can organize organize them?

Let's look at the following figure:

Balls and Lines

For 4 boxes, we only need 3 lines to separate the balls into 4 different groups. For the above figure, it corresponds to:

$\f[\begin{cases} x_1 &= 2 \\ x_2 &= 2 \\ x_3 &= 0 \\ x_4 &= 2 \end{cases}\f]$

To count the number of solutions, let's imagine that we have 9 empty spaces. Each spaces can hold either a ball or a line. After we put 6 balls and 3 lines into it, we have 1 solution to the system. The total number of solutions is just $\f$\binom{6+4-1}{6}\f$$ . For general n and k, the solution is:

$\f[\binom{n+k-1}{n}\f]$

which means we choose n balls out of n+k-1 of items.

Recurrence Approach

First, let $\f$S_k^n\f$$ be the number of solution for the equation.

Now, consider if we increase the value of k by 1. To do so, we have 1 more variable, $\f$x_{k+1}\f$$ , and it can take values from 0 to n. When $\f$x_{k+1} = i\f$$ , the other variables need to be summed to n-i. So the number of solution is $\f$S_k^{n-i}\f$$ .

Therefore, we have:

$\f$\displaystyle S_{k+1}^n&=\sum _{i=0}^n S_k^{n-i} \f$$

$\f$\displaystyle \displaystyle S_{k+1}^n&=\sum _{i=0}^n S_k^i\f$$ ..............................(1)

If we repeatedly apply (1) to itself, we have:

$\f$\displaystyle S_k^n=\sum _{n_1=0}^n \sum _{n_2=0}^{n_1} \sum _{n_3=0}^{n_2} \text{...}\sum _{n_{k-1}=0}^{n_{k-2}} S_1^{n_{k-1}}\f$$ ................................(2)

$\f$\displaystyle \displaystyle \displaystyle S_k^n=\sum _{n_1=0}^n \sum _{n_2=0}^{n_1} \sum _{n_3=0}^{n_2} \text{...}\sum _{n_{k}=0}^{n_{k-1}} S_0^{n_{k}}\f$$ .......................................(3)

Therefore, if we solve (1), we will find the repeated sum of the form (2) or (3).

Partial Difference Equation

Equation (1) is still too difficult to be solved. Therefore, I simplify it using telescope method:

$\f$S_{k+1}^{n+1}-S_{k+1}^n=\sum _{i=0}^{n+1} S_k^i-\sum _{i=0}^n S_k^i\f$$

$\f$S_{k+1}^{n+1}-S_{k+1}^n=S_k^{n+1}\f$$ ...........................................................................(4)

(4) is a partial difference equation that can be easily solved using generating function method.

Generating Function

Define:

$\f[S_k(x)=\sum _{n=0}^{\infty } S_k^nx^n\f]$

Multiple (4) by $\f$x^{n+1}\f$$ and do a summation on k from zero to infinite, we have:

$\f[\begin{align*} S_k(x)&=\frac{1}{1-x}S_{k-1}(x) \\ S_k(x)&=\frac{1}{(1-x)^{k-1}}S_1(x) \end{align*}\f]$

We stopped at k = 1, since $\f$S_0^n = 0\f$$ . Now, let's find out what's $\f$S_1(x)\f$$ first.

$\f[S_1(x)=\sum _{n=0}^{\infty } S_1^nx^n\f]$

From the definition of S, we know that:

$\f[S_1^n = 1\f]$ since for 1 variable to sum to n, we only have 1 solution, that is x = n.

Therefore:

$\f[S_1(x)&=\frac{1}{1-x}\f]$

Now, we have:

$\f[S_k(x)=\frac{1}{(1-x)^{k}}\f]$ To find out the explicit form of S, we do a power series expansion on S:

$\f[\begin{align*} S_k(x)&=\sum _{n=0}^{\infty } \binom{-k}{n}(-x)^n\\ &=\sum _{k=0}^{\infty } \binom{n+k-1}{n}x^n \end{align*} \f]$
So the explicit form of S is:

$\f[S_k^n= \binom{n+k-1}{n} \f]$ From (2), we have found the following formula:

$\f[\sum _{n_1=0}^n \sum _{n_2=0}^{n_1} \sum _{n_3=0}^{n_2} \text{...}\sum _{n_{k-1}=0}^{n_{k-2}} 1 = \binom{n+k-1}{n}\f]$

Other Summation Function

For any other $\f$a_k\f$$ , we set $\f$S_0^n = a_n\f$$ .

$\f[\begin{align*} S_k(x)&=\frac{1}{(1-x)^k} S_0(x)\\ &=\sum _{n=0}^{\infty } a_nx^n\sum _{n=0}^{\infty } \binom{n+k-1}{n}x^n \\ &= \sum _{n=0}^{\infty } \left(\sum _{j=0}^n \binom{n+k-j-1}{n-j}a_j\right)x^n \end{align*} \f]$

Therefore we found the following repeated sum:

$\f[\sum _{n_1=0}^n \sum _{n_2=0}^{n_1} \sum _{n_3=0}^{n_2} \text{...}\sum _{n_{k}=0}^{n_{k-1}}a_{n_{k}} = \sum _{j=0}^n \binom{n+k-j-1}{n-j}a_j\f]$

Conclusion

I have solved the problem of finding the number of solutions to the equation:

$\f[x_1+x_2+\text{...}+x_k=n\f]$

with non-negative integral solutions. I first gave an combinatoric approach which is more easy. Then I solve the problem in another way by transforming the problem to a partial difference equation. The solution is found to be:

$\f[S_k^n= \binom{n+k-1}{n} \f]$

And using similar approach, I found out the formula for repeated sum as well: