• Mathematical Induction

    • base step: P(1)
    • Inductive step: for all k, assume P(k): P(k) ⇒ P(k+1)
    • therefore for all n P(n)

  • Strong Induction

    • base step: P(1)
    • Inductive step: for all k, assume P(1) & P(2) & … P(k) ⇒ P(k+1)
    • therefore for all n P(n)

  • ex) Fundamental Theorem of Arithmetic

    • all integer can be written as product of primes

      Untitled

  • Recursion

    • basis step: specify the value at zero

    • recursive step: find value at smaller integers(문제를 쪼갬)

      • fibonacci

    • ex) String

      • basis: empty string lambda

      • recursive: w,x in SIGMA→ wx in SIGMA

        Untitled

    • ex) Well-formed fomulae

      • basis: T,F,p is well formed
      • recursive: if A and B is well, ~A, A and B, A or B, A → b, A ↔B is well

    • ex) Rooted Trees

      • basis: single vertex r is rooted tree
      • recursive:
        • suppose T1,…,Tn: disjoint rooted trees
        • add all roots at r →rooted tree

    • ex) Full Binary Tree

      • every node have zero/2 children
      • finding height
        • basis: root: height=0
        • recur: h(T) = 1+ max(T1, T2)
      • number of vertices
        • basis: root: n(T) = 1
        • recur: n(T) = 1+n(T1)+n(T2)

    • ex) factorial

    • ex) GCD

    • ex) binary search

    • ex) merge sort

      Untitled