Sum of Numbers from 1 to N... A relatively uninteresting proof...

 Alright. Let's do a simple problem. It may come up in programming interviews, and you can present them with this not-at-all-computer-sciencey solution:

"What is the sum of all integers from 1 to N?"

Hmmm, well, I'm just going to pull something random out of a hat... how about n*(n+1)/2... Yeah... That sounds good. Now, let's prove this by induction.

Base Case: n = 1

1 * (1+1)/2 = 1*1 = 1... Yep. Since the sum of all integers from 1 to 1 is well... 1, the statement holds for this case.

Inductive Step: Must prove that if n*(n+1)/2 holds for n, then (n+1)*(n+2)/2 holds for n+1.

Well, the sum from 1 to n+1 = (sum from 1 to n) + (n+1) = n*(n+1)/2 + (n+1) = (n+1)*((n/2) + 1)=(n+1)*(n+2)/2...

So, this demonstrates that it holds for n = 1 -> it holds for n = 1+1 = 2 -> n = 3 -> etc.

I promise I'm working on a much more interesting post. But that's a difficult one to write. I might just do the root 2 is irrational proof tomorrow...