>Therefore, what
> type of proof is expected below?
A convincing proof :)
> Question 3.1 asks us to "prove that a binary tree with N nodes
> has N+1 null pointers."
Somebody wants to know which of the numbers
8+6, 8^2+6, 8^3+6, 8^4+6, ...
can be divided by 7. He starts calculating and notices:
8+6 = 14 is divisible by 7
8^2+6 = 70 is divisible by 7
8^3+6 = 518 is divisble by 7
8^4+6 = 4102 is divisble by 7
Can he be certain that this will go on indefinitely -- no, not yet. Does it make sense
to calculate
more examples? Not really.
But now he notices:
8^5+6 = 8*8^4+6 = 7*(8^4) + (8^4+6) = multiple-of-7 + multiple-of-7 =
multiple-of-7
8^6+6 = 8*8^5+6 = 7*(8^5) + (8^5+6) = multiple-of-7 + multiple-of-7 =
multiple-of-7
8^7+6 = ...
Once he sees this, he can be assured that this will continue forever, because in each
of those
steps, the same trick applies.
A sample proof.
Statement: for all integers n (n > 0): 2^n >= n
Proof.
Let's call a number n "nice" if 2^n >= n.
1. 1 is nice: you can verify this by direct calculation: 2^1 = 2 >= 1
2. Every number has a nice successor.
Proof: If k is nice and m is its successor, then
2^m = 2^(k+1) = 2*2^k >= 2*k = k+k >= k+1 = m, and so m is nice too.
3. According to (1) 1 is nice, so according to (2) 2 also is nice, so according to (2)
3 also has to
be nice, ... In other words, from (1) and (2) it follows that every integer n (n>0) is
nice.
Hans
