I recently got an email forward from my Mom.  It went something like "Pick your favorite number.  Multiply it by 3, add 3 to that number, then multiply the resulting number by 3.  Take the digits of this number and add them together, repeat until you have a single digit number.  Take this number and look it up on the following table, this person is your role model."  She had put her name in at number 9.  Immediately I wondered, "How does this work?"  Some quick math shows:

3 * (3 * N + 3) 3 * 3 * N + 3 * 3 9 * N + 9 9 * (N + 1)

Therefore, regardless of what number you pick initially, the result is always a multiple of nine.  But how do we know that adding the digits will always result in 9?  When I was in elementary school, someone told me an easy way to remember the multiples of 9.  Write the numbers from 0 to 9 in a column, then next to them write the numbers from 9 to 0:

09 18 27 36 45 54 63 72 81 90

As you can see, if you sum the digits of all of these multiples you wind up with 9.  I've run over some more multiples in my head, and you always end up with either 9 or a multiple of 9.  But how do you prove that?  I don't remember much from my Introduction to Proofs class, so excuse my sloppy notation.

Given:

• Let m be an integer
• Let n = 9m (n is therefore a multiple of 9)
• Let d_k be the digits of n.  That is, d₀, d₁, ..., d_k are integers such that
  
  

Prove:

There exists an integer j such that

Note:I found a pretty cool equation generator here.