Chances of (random(0,n) + random(0,n) <= m)

From: Brendan Sechter (sgeos_at_granicus.if.org)
Date: 11/03/04 

Date: 3 Nov 2004 12:05:24 -0800

If I am going pick two numbers at random, both from zero to n and add
them, what is the chance of the sum being less than or equal to m?

This seems like it should be easy, but my math is really rusty.

If n is 5 and m is 3 I can draw this diagram:

     | m n
     | 0 1 2 3 4 5
-----+-----------------------
     |
  0 | 0 1 2 3 / 4 5
     | /
  1 | 1 2 3 / 4 5 6
     | /
  2 | 2 3 / 4 5 6 7
     | /
m 3 | 3 / 4 5 6 7 8
     | /
  4 | 4 5 6 7 8 9
     |
n 5 | 5 6 7 8 9 10

The chance of the random sum being less than m is 10 / 25. If m is
less than or equal to n, the chances are 0 + 1 + ... m + (m + 1).

If m is greater than n, the chances are n squared minus something. I
can see the "something", but I'm having trouble putting it in terms of
m and n. I'm also not happy with an if-else answer.

Side note: What is my real problem?
This is a death spell calculation that may be used in a game. n is
the spell's power level and m is the target's remaining life. It
would be nice to be able to display the chance of killing the target.
It's not strictly necessary that I understand why a given solution
works, but as a matter of personal pride I'd like to.

-Brendan