Recursive programming will be tough to apply without understanding induction, and you will find that many fractal problems can be
implemented recursively with much less code than an iterative solution. Therefore, I am going to spend some time on induction. If you already
understand it, feel free to skip ahead.
Intuitive Mathematical induction
It is a no-brainer for a human being to "see" that, if the first domino falls, all of the dominos will fall. Believe it or not, your brain
just proved it using induction. Step one, the base case, the first domino falls = true. That truth is the fact we use to prove that
the second domino will fall i.e. the truth of that statement in step one implies the truth of the following step Step two, the inductive step, if any domino falls, the next domino will fall. Let's do that with numbers.
Sum of Integers
The iterative solution is pretty simple.
Now the recursive solution
TRY IT Enter a positive integer
There is an easier way!
I'm not sure who invented (or discovered, depending on your point of view) the formula for the sum of integers (probably Gauss), but it is commonly used
to demonstrate induction. It is this: The sum of integers
between 1 and N = N*(N+1)/2 *this is the kind of stuff that makes us like math!
Prove it
Let N=3. Well, 3*4/2 = 6. That's right! but that only proves it is true for the integer 3, and we want to prove it for all integers.
To do that, we need to do two things
Prove that it is true for a base case (recall the base case of recursion)
Show that the Proof for the base-case integer implies that the formula is true for the next consecutive integer
That's a mouthful. What we are shooting for is a logical implication where, If A implies B = true, & A is true, then B must be true.
We already know that A is true; that was our base case. The second step is called the inductive step where we prove that A implies B is true.
Original Formula: N*(N+1)/2
Let's take the formula and add the next consecutive integer to it. I.e. N+1
We get (N*(N+1)/2)+ N+1 (if our N was 3, we just added 4 to it with N+1) Using actual integers we have
(3*(3+1)/2)+3+1 = 10.
If we substitute (N+1) for every N in our original formula we have (N+1)*(N+1+1)/2.
Using actual integers that would be (3+1)*(3+1+1)/2 = 10.
If we can show that (N*N+1/2)+N+1 equals (N+1)*(N+1+1)/2 then this formula is true for all N's
Using some Algebra
simplify it a bit: N2+1)/2 +N+1 does it equal (N+1)*(N+2)/2
Multiply each term by 2: N2+3N+2 does it equal (N+1)(N+2)
Factor the left side: (N+1)(N+2) does it equal (N+1)(N+2)
Looks like it is true for all N.
Induction like Recursion is not always obvious (another induction example)
Recursive solutions can be intuitively different just as induction proofs are. So hang in there with me through one more induction proof and you will
see what I mean when we compare the factorial and Towers-of-Hanoi solutions. Again N is an positive integer.
Suppose we wanted to prove (using induction) that 3N-1 is a multiple of 2. We do not have a very clear equation here.
Remember "... 55 minutes thinking about the problem..."
First, Prove the base case: 32-1 = 8, which is a multiple of 2 because 8%2=0 (modulo operator).
For the Inductive step, we need to substitute N+1 wherever there was an N in the original equation. Is 3N+1-1 a multiple of 2?
If so, it is true for all N
There are two ways (that I can think of) to do this:
Prove the two equations are logically equivallent using modular arithmetic
Show that both equations = 0 and therefore, each other
The latter is easier.
From our knowledge of exponents we can say that 3n+1-1 = 3n * 31 -1.
3n * 31 -1 = 3n * 3 -1 = 2*3n + 1*3n -1
We can show that say that 2*3n %2 = 0 because any integer *2 and then %2 will = 0.
Powers of 3 are always odd because any odd number * another odd number = an odd number.
Any odd number -1 as in 1*3n -1 is an even number, and any even number %2 = 0.
