### Component

- Base Case
- 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: **

**simplified the formula:**

**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

## 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.

## 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.