Component

  1. Base Case
  2. Recursive formula

$\sum^n_{i=1}i$ can be define as

  • g(1)=1
  • g(n)=g(n-1)+n, for all $n\geq2$

Proportional sequence

$$\sum^k_{i=0}a^i=\frac{1-a^{k+1}}{1-a}$$

Close form

we use “unrolling" as a organized technique to get he simplest form of recursive steps. The main idea of it is to substitute itself

T(1) = 1

T(n) = 2T(n-1)+3 for all $n\geq 2$

substitute itself:

step 1
step 1

simplified the formula:

step 2
step 2

determine the base case:

in our case, T reach the base base when its input is 1 i.e. $n-k = 1$.; Then, we substitute $k=n-1$ back into the formula, we get

step 3
step 3

Divide and conquer

divided problem n into a sub-problems, each of size $n/b$, write as

$$ S(n)=aS(n/b)+f(n) $$

Hypercubes

the recursive step can also be applied in non-numerical object

Q0 is a single node with no edges
Qn consists of two copies of Qn−1 with edges joining corresponding nodes, for any n ≥ 1.

recursive graph
recursive graph

Proof

always suitable to induction proof, we should often mirrors the structure in order to prove

F represent Fibonacci numbers, claim: For any n ≥ 0, $F_{3n}$ is even.

We proof by induction on n

Base: $f_0=0$, which is even

Induction: Suppose $F_{3n}$ is even for $n=0,1,...,k$. we need to show that $F_{k+1}$ is even

$$ F_{3(k+1)}=F_{3k+3}=F_{3k+2}+F_{3k+1} $$

because $F_{3k+2}=F_{3k+1}+F_{3k}$, substitute back into the function, we get

$$ F_{3(k+1)}=2F_{3k+1}+F_{3k} $$

By the induction hypothesis, $F_{3k}$ is even and $2F_{3k+1}$ is also even since it is 2 times an integer. Therefore, $F_{3(k+1)}$ is even.

Q.E.D.

When the recursive step include the definition of recursive steps, we should use the strong induction to prove the claim.

let define the function f as:

f(0) = 2f

(1) = 3

for all $n\geq 1, f(n+1)=3f(n)-2f(n-1)$

prove the claim that: for all n, $f(n)=2^n+1$

we prove by induction on

Base: f(0) is define to be2 2; f(1) is define to be 3

Induction: Suppose $f(n)=2^n+1$ for $n=0,1,...,k$

$$ f(k+1)=3f(k)-2f(k-1) $$

By the induction hypothesis, $f(k)=2^k+1$ and $f(k-1)=2^{k-1}+1$

Substitute these formulas into the previous equation, we get

$$ f(k+1)=2^{k+1}+1 $$

Q.E.D.