Recurrence problem

When I read some books, i found solving Towers of Hanoi problem let me understand the whole process of proof.

Everyone knew Hanoi problem. So the recursive solution has three stages.
Stage1:  Move the top n-1 disks from the first post to the first post to the second using the solution for n -1 disks. This can be done in Tn-1 steps.
Stage2: Move the largest disk from the first top to the third post. This takes just 1 step.
Stage3: Move the n - 1 disks from the second post to the third post, again using the solution for n - 1 disk. This can also be done in Tn-1 steps.

This algorithm shows that Tn, the minimum number of steps required to move n disks to a different post, is at most Tn-1 + 1 + Tn-1 = 2Tn-1 + 1.

So we can find a recurrence.

T1 = 1
Tn = 2Tn-1 + 1  for n >= 2

So we can use this recurrence to compute any number of terms in the sequence:
T1 =1
T2 = 2T1 + 1 = 3
T3 = 2T2 + 1 = 7
T4 = 2T3 + 1 = 15
...

Let us prove this Claim

the proof is by induction on n. The induction hypothesis is that Tn = 2^n - 1. This is true for n = 1 because T1 = 1 = 2^1 -1.
Assume that Tn -1 = 2^(n-1) -1 in order to prove that Tn = 2^n -1. Where n >= 2
Tn = 2Tn-1 + 1 = 2(2^(n-1) - 1 ) + 1 = 2^n -1

The first equality is the recurrence equation, the second follows from the induction assumption, and the last step is simplification.

Chapter 1: Complete Induction

Sometimes, I cannot understand the meaning of Complete Induction.  I always confuse how to use it. I have an example here which gets from “How to prove it”.

Sample: Suppose n is an integer larger than 1 and n is prime. Then P(n): 2^n -1 is prime.

We can see

n = 2, 2^n – 1 = 3

n = 3, 2^n – 1 = 7

n = 5, 2^n – 1 = 31

Then, the next prime number 7 is in N. The expression holds for every prime number less than 7. So, from complete induction, P(7)  holds. Similarly, the expression holds too for next prime number 11. Such that, I get conclusion that P(n) holds for every prime number. As a matter of fact, everyone knows this predict is not correct. But I cannot figure out where is wrong with my proof.

The definition of Complete Induction is described for all natural numbers. In this sample, I do not use 4 and 6 in the proof because they are not prime number. Does this not obey the rule of Complete Induction? I do not think so.  At ton of proofs, we define the base case which is from bigger numbers than 1. That means the domain of variable may not include all natural numbers.

Chapter 0: sample

Let’s start my first blog of csc236.

In the chapter 0 Preliminaries of Notes (“Notes” below), the author defines “Partial Order” is “if R is antisymmetric and transitive”. At first, I thought the definition is wrong because this definition of this term in the “How to prove it” (“How” below) is “if R is reflexive, transitive, and antisymmetric”. As if the definition in Notes is missing reflexive. From definition 4.4.1 of “How”, R is said to be antisymmetric if x in A and y in A then xRy and yRx implies x = y. Base on that, xRy and yRx are correct if antisymmetric holds. That could to say that antisymmetric includes reflexive, I guess.

The reason of confusion is the sample R3 in the Notes. R3={(a,b): a and b are persons and a is an ancestor of b}. Notes explains that R3 is a partial order. Form definition of reflexive, we can image from R3: I and I are persons and I am ancestor of I. Oh, I become my daddy, or I am my son, so I am I. Does it sound weird? Of course, there is not any defect in the logic. But, I do not think this sample could help us to understand the term. So, this sample is used in the notes is not reasonable.

This is my personal opinion.