Ways of Summing Odd Numbers

You may have seen the solution by Class 2YP from Madras College to a problem which they were inspired to consider after working on the problem called Score from the June Six. They investigated the number of ways of expressing an integer as the sum of odd numbers.

I'd like to introduce the following notation: let $P_x(n)$ be the number of ways in which $n$ can be expressed as the sum of $x$ odd numbers where we only count each set of $x$ numbers once, that is we ignore the order in which the numbers occur.

To start with, class 2YP found that $P_2(n) = n/4$ when $n$ is divisible by 4 and $P_2(n) = (n+2)/4$ when $n$ is an even number not divisible by 4. If the even number $n$ is equal to $2k$, then the number of odd numbers less than $n$ is $k$. For each of the $k$ odd numbers there will be another such that the sum of the two is $n$ and the two cases occur according to whether $k$ is even or odd. It will probably be much more difficult to show conclusively that their result concerning 3 odd numbers is correct.

If you want to solve the problem differently, you might be interested in programming a computer to find the number of solutions for you. To do this you would need to consider how to limit your search. First of all, you should start with a trick which often comes in handy if you are trying to find a certain number of solutions and the order doesn't matter, that is to label them $a,b,c$ and define them so that $a\leq b\leq c$. In this problem $a+b+c=n$. This way none of the solutions are repeated by having the same numbers in a different order.

Now that we've done that, we can also say that $c$ is at least the smallest odd integer greater than or equal to $n/3$ (where n is the required total). This is evident when you consider that $c$ is defined to be the largest of $a,b,c$ and that they must sum to $n$. Clearly $c$ is also no more than $n-2$. This restricts the range of values of $c$ to the interval $n/3 \leq c \leq n-2$.

Once we've decided the range of possibilities for $c$, the possibilities for $a$ can also be limited. The smallest possible value of $a$ is $a= n-2c$ (which occurs when $n-2c> 0$ and $b=c$) and the largest is $a=(n-c)/2$ (which occurs when $a=b$).

Now all that remains is to count the number of possibilities for $a$ for each possible value of $c$. This will be the number of solutions to the problem because for each pair $\{a,c\}$ there is exactly one set $\{a,b,c\}$ such that $a+b+c=n.$ This algorithm may be of interest to the computer buffs among you who may be interested in extending the problem by writing a program.

If you try just counting out the solutions in this way when $n$ is a large number like 1999, you'll be there for a long time. For those of you who may wish to explore it from more of a pure mathematical perspective, you might like to try to prove some of the results which class 2YP found.

If you would like to explore this from a different angle, look at the following table:

The table above shows the number of ways of summing any 3 numbers to achieve the required total $t$. If you thought that the pattern forming above looked suspiciously similar to that which we saw previously for only odd numbers, you would be correct, as I am about to demonstrate.

The equation $a + b + c = n$ (for odd $a,b,c,n$) has as many solutions as this equation: $$(a+1) + (b+1) + (c+1) = (n+3).$$ Each of the bracketed quantities is even, so dividing through by a factor of 2 gives $$x + y + z = t $$ where $x,y,z$ are any integers, and $t$ is any integer greater then 2. You might find it easier to work with this version of the problem in your attempt to prove class 2YP's formula. I didn't think it was easy to find a solid proof with either of them, so I'd be interested to hear from you if anyone makes any progess.

Another obvious way of extending the problem is to try considering the number of ways of expressing a number as the sum of four odd numbers, or five or more... But I warn you, it gets harder!