Week 12 - Recursion B

6.201 Recursive definitions

  • Recursion
    • When you must define a math object (set, func, sequence) in terms of object itself.
  • Recursively defined functions
    • Recursively defined function f with domain N\mathbb{N} is defined by:
      • BASIS STEP: specify an initial value of function.
      • RECURSIVE STEP: rule for defining value of function when given integers, in terms of smaller integers.
    • We call this definition: recursive or inductive.
    • Defining a function f(n)f(n) from set N\mathbb{N} to set R\mathbb{R} is same as sequence: a0,a1a_0, a_1 ... where iN\forall i \in \mathbb{N}, aiRa_i \in \mathbb{R}
    • Examples
      • Give recursive definition of sequence {an},n=1,2,3,...\{a_n\}, n = 1, 2, 3, ... in following cases:
        • an=4na_n = 4n
        • an=4na_n = 4^n
        • an=4a_n = 4
      • May be more than one correct answer to each sequence
          1. As each term in the sequence is greater than the previous term by 4, this sequence can be defined by setting a1=4a_1 = 4 and declaring that n1 an+1=4+an\forall n \ge 1 \ a_{n+1} = 4 + a_n
          1. As each term is 4 times its predecessor, this sequence can be defined as a1=4a_1 = 4 and n1 an+1=4an\forall n \ge 1 \ a_{n+1} = 4a_n
          2. a1=4a_1 = 4
          3. a2=42=44=16a_2 = 4^2 = 4 * 4 = 16
          4. a3=43=416=64a_3 = 4^3 = 4 * 16 = 64
          5. a4=44=464=256a_4 = 4^4 = 4 * 64 = 256
          1. Sequence can be defined as a1=4a_1 = 4 and n1 an+1=an\forall n \ge 1 \ a_{n+1} = a_n
  • Recursively defined sets
    • Like sequences, for some sets, defining recursively is easier than defining explicitly.
    • Sets can also be defined recursively, by defining two steps:
      • BASIS STEP: where we specify some initial elements.
      • RECURSIVE STEP: provide a rule for constructing new elements from those we already have.
    • Example
      • Consider the subset of S of the set of integers recursively defined by:
          1. BASIS STEP: 4S4 \in S (4 is an element of S)
          1. RECURSIVE STEP: if xSx \in S and ySy \in S then x+ySx + y \in S
      • We will be shown later how we can prove that set S is the set of all positive integers that are multiples of 4.
  • Recursive algorithms
    • Algorithm
      • A finite sequence of precise instructions for performing a computation or solving a problem.
      • An algorithm is considered recursive if it solves a problem by reducing to an instance of the same problem with smaller input.
    • Example

      • Let's give a recursive algorithm for computing n!n! where n is a nonnegative integer:
        • n! can be recursively defined by the following 2 steps:
          • BASIS STEP: 0!=10! = 1
          • RECURSIVE STEP: n!=n(n1)!n! = n (n - 1)! where nn is a positive integer.
        • The pseudocode of the algo can be formalised as:

      procedure factorial(n: nonnegative integer) { if n = 0 then return 1 else return n factorial (n - 1) }

Lesson 6.204 Recurrence relations

  • Recurrence Relation
    • An equation that defines a sequence based on a rule which gives the next term as a function of the previous term.
  • Infinite Sequence
    • Function from the set of positive integers to set of real numbers.
  • It can be useful to formalise the problem as sequence before solving it.
  • Example: [[Towers of Hanoi]]
    • ![[week-12-hanoi-tower.png]]
    • Want to get discs from spoke A to C.
    • Can only move one disk at a time.
    • You cannot place a larger disc on a smaller one.
    • It is an example of a recursive function.
    • Number of moves:
      • Let ana_n be min number of moves to transfer n from one spoke to another.
      • To move n discs from A to C, we must move n-1 discs from A to B by an1a_{n-1} moves.
      • Then, move last (and largest) disc from A to C by 1 move.
      • Then, remove the n-1 discs again from B to C by an1a_{n-1} moves.
      • Thus, total moves is an=2an1+1a_n = 2a_{n-1} + 1
  • Linear Recurrence
    • In which each term of a sequence is a linear function of earlier terms in the sequence.
    • Two types of linear recurrence:
      • Linear homogeneous recurrence:
        • formalised as an=c1an1+c2an2+...+ckank\mathbf{a_n} = c_1\mathbf{a_{n-1}} + c_2\mathbf{a_{n-2}}+... + c_k\mathbf{a_{n-k}}
        • where c1,c2,...,ckRc_1, c_2, ..., c_k \in \mathbb{R}, and k is the degree of relation.
      • Linear non-homogeneous recurrences:
        • formalised as an=c1an1+c2aa2+...ckank+f(n)\mathbf{a_n} = c_1\mathbf{a_{n-1}} + c2\mathbf{a_{a-2}} + ... ck\mathbf{a_{n-k}} + f(n)
        • where c1,c2,...,ckRc_1, c_2, ..., c_k \in \mathbb{R}, and f(n) is a function.
        • Depending only on n, and k is the degree of relation.
    • Example: first order recurrence
      • Consider:
        • a country has 50 million people that:
          • has population growth rate (birth rate - death rate) of 1% per year.
        • receives 50,000 immigrants per year.
      • Question: find this country's population in 10 years.
      • This case can be modelled as the following first-order linear recurrence:
        • where ana_n is the population in n years from now.
        • nN\forall n \in \mathbb{N}, an+1a_{n+1} is expressed as an+1=1.01an+50,000a_{n+1} = 1.01 \mathbf{a_n} + 50,000
        • a0=50,000,000a_0 = 50,000,000.
    • Example: 2nd order recurrence
      • Consider:
        • 0, 1, 1 2, 3, 5, 8, 13, 21, 34, ...
        • where each number is found by adding up the two numbers before it.
      • We can model the sequence as 2nd-order linear recurrence:
        • an=an1+an2a_n = a_{n-1} + a_{n-2}
        • a0=0a_0 = 0
        • a1=1a_1 = 1
      • This is called Fibonacci sequence.
  • Arithmetic sequences
    • We consider a sequence arithmetic if distance between consecutive terms is a constant c
    • n\forall n, an+1a_{n+1} is expressed as an+1=an+ca_{n+1} = a_n + c and an=aa_n = a
    • Example:
      • Sequence 2, 5, 8, 11, 14, ... is arithmetic with initial term of a0=2a_0 = 2 and a common difference of 3.
      • 30, 25, 20, 15, ... is arithmetic with initial term of a0=30a_0 = 30 and common difference of -5.
  • Geometric sequences
    • Sequence is geometric if ratio between consecutive terms is a constant r.
    • n\forall n, an+1\mathbf{a_{n+1}} is expressed as an+1=r ana_{n+1} = r \ \mathbf{a_n} and a0=a\mathbf{a_0} = a
      • Example:
        • Sequence 3, 6, 12, 24, 48, ... is geometric with an initial term of a0=3a_0 = 3 and a common ratio of 2.
        • 125, 25, 5, 1, 1/5, 1/25, ... is geometric with initial term of a0=125a_0 = 125 and common ratio of 1/5.
  • Divide and conquer recurrence
    • Divide and conquer algorithm consists of three steps:
      • dividing problem into smaller subproblems.
      • solving (recursively) each subproblem.
      • combining solutions to find a solution to original problem.
      • Example:
        • Consider the problem of finding minimum of a sequence {an}\{a_n\} where nNn \in \mathbb{N}
          • if n=1, the number is itself min or max.
          • if n > 1, divide the numbers into 2 lists.
          • order the sequence.
          • find min and max in first list.
          • find min and max in second.
          • infer the min and max of entire list.

Lesson 6.206 Solving recurrence relations

  • Solving linear recurrence
    • Let an=c1 an1+c2 an2+...+ck anka_n = c_1 \ \mathbf{a_{n-1}} + c_2 \ \mathbf{a_{n-2}} + ... + c_k \ \mathbf{a_{n-k}} be a linear homogeneous recurrence.
    • If a combination of the geometric sequence an=rna_n = r^{n} is a solution to this recurrence, it satifies rn=c1 rn1+c2 rn2...ck rnkr^n = c_1 \ r^{n-1} + c_2 \ r^{n-2} ... c_k \ r^{n-k}
    • By dividing both sides by rnkr^{n-k}, we get: rk=c1 rk1+c2 rk2...ck\mathbb{r^{k}} = c_1 \ \mathbb{r^{k-1}} + c_2 \ \mathbb{r^{k-2}} ... c_k
    • We call this equation the Characteristic Equation.
      • Solving this equation is first step towards finding a solution to linear homogeneous recurrence:
        • If rr is a solution equation with multiplicity p, then the combination (λ+βn+yn2+...+μnp1)rn(\lambda +\beta n + yn^2 + ... + \mu n^{p-1})\mathbf{r^{n}} satisifes the recurrence.
  • Solving Fibonacci recurrence
    • Let's consider solving the Fibonacci recurrence relation: fn=fn1+fn2f_n = f_{n-1} + f_{n-2}, with f0=0f_0 = 0 and f1=1f_1 = 1
      • Solution:
        • The characteristic equation of the Fibonacci recurrence relation is: r2r1=0r^2 - r - 1 = 0
        • It has 2 distinct roots, of multiplicity 1:
          • r1=(1+5)/2r_1 = (1 + \sqrt{5}) / 2 and r2=(15)/2r_2 = (1 - \sqrt{5}) / 2
        • So, fn=α1 r1n+α2 r2nf_n = \alpha_1 \ r_1^{n} + \alpha_2 \ r_2^n is a solution.
      • To find α1\alpha_1 and α2\alpha_2 we need to use the initial conditions.
        • From:
          • f0=α1+α2=0f_0 = \alpha_1 + \alpha_2 = 0
          • f1=α1(1+5)/2+α2(15)/2=1f_1 = \alpha_1(1 + \sqrt{5})/2 + \alpha_2 (1 - \sqrt{5})/2 = 1
        • By solving the 2 equations, we can find α1=1/5\alpha_1 = 1/\sqrt{5} and α2=1/5\alpha_2 = -1 / \sqrt{5}
      • The solution is then formalise as:
        • fn=1/5.(((1+5)/2)n)1/5.(((15)/2)n)f_n = 1 / \sqrt{5} . (((1 + \sqrt{5}) / 2)^{n}) - 1/\sqrt{5} . ((( 1 - \sqrt{5})/2)^{n})
  • Example 2
    • Consider another sequence
      • an=3an13an2an3a_n = -3a_{n-1} - 3a_{n-2} - a_{n-3}
      • a0=1,a1=2 and a2=1a_0 = 1, a_1 = -2 \text{ and } a_2 = -1
      • Solution:
        • The characteristic equation of this relation is: r3+3r2+3r+1=0r^3 + 3r^2 + 3r + 1 = 0
        • It has a distinct root, whose multiplicity is 3, r1=1r_1 = -1
        • So, an=(α0+α1n+α2n2)r12a_n = (\alpha_0 + \alpha_1n + \alpha_2n^2)r_1^2 is a solution
      • To find α0,α1\alpha_0, \alpha_1 and α2\alpha_2 we need to use initial conditions.
        • From:
          • a0=a0=1a_0 = a_0 = 1
          • a1=(α0+α1+α2)=2a_1 = -(\alpha_0 + \alpha_1 + \alpha_2) = -2
          • a2=(α0+2α1+4α2)=1a_2 = (\alpha_0 + 2\alpha_1 + 4\alpha_2) = -1
        • We can find α1=3,α2=2\alpha_1 = 3, \alpha_2 = -2
      • The solution is then formalised as: an=(1+3n2n2)(1)na_n = (1 + 3n - 2n^2)(-1)^{n}
  • Using strong induction to solve recurrence
    • It is sometimes easier to solve recurrence relation solutions using strong induction.
    • Example:
      • Prove:
        • P(n): the sequence f_n = 1/\sqrt{5}(r_1^{n} -r_2^{n}) verifies the Fibonacci recurrence, where:
          • r1=(1+5)/2r_1 = (1 + \sqrt{5}) / 2
          • r2=(15)/2r_2 = (1 - \sqrt{5}) / 2 are the roots of r2r1=0r^2 - r - 1 = 0$
        • First, verify for P(2):
          • f1+f0=1/5(r1r2)=1/5(5)=1=f2f_1 + f_0 = 1 / \sqrt{5}(r_1 - r_2) = 1/\sqrt{5} (\sqrt{5}) = 1 = f_2
          • because f2=1/5(r12r22)=1f_2 = 1/\sqrt{5}(r_1^2 - r_2^2) = 1
          • which verifies the initial condition.
        • Let kNk \in \mathbb{N}, where P(2), P(3) ... P(k) are all true.
        • Let's verify P(k+1)P(k+1):
          • fn+fn1=r1nr225+r1n1r2n25=r1n1(r1+1)/5+r2n2(r2+1)/5=r1n1r12+r2n1r22=r1n+1+r2n+1f_n + f_{n-1} = \frac{r_1^n - r_2^2}{\sqrt{5}} + \frac{r_1^{n-1}-r_2^{n-2}}{\sqrt{5}} = r_1^{n-1}(r_1 + 1) / \sqrt{5} + r_2^{n-2}(r_2 + 1) / \sqrt{5} = r_1^{n-1} * r_1^{2} + r_2^{n-1}* r_2^{2} = r_1^{n+1} + r_2^{n+1} which equals fn+1f_{n + 1}
        • We can conclude that P(k+1)P(k+1) is true and the strong induction is verified.

Assignment 6.209 - Induction and Recursion

Use mathematical induction to prove that nN\forall n \in N

P(n):123+234++n(n+1)(n+2)=n(n+1)(n+2)(n+3)/4P(n) : 1 · 2 · 3 + 2 · 3 · 4 + ··· + n(n + 1)(n + 2) = n(n + 1)(n + 2)(n + 3)/4

Answer

  1. BASIS STEP

The basis step P(1)P(1) is true because:

123=1(1+1)(1+2)(1+3)41 * 2 * 3 = \frac{1(1 + 1)(1 + 2)(1 + 3)}{4}

  1. INDUCTION STEP

Let kk be an arbitrary element, where P(k)P(k) is true.

P(k)=123+234+...+k(k+1)(k+2)=k(k+1)(k+2)(k+3)4P(k) = 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + ... + k(k + 1)(k + 2) = \frac{k(k+1)(k+2)(k+3)}{4}

Verify P(k+1)P(k + 1)

P(k+1)=123+234+...k(k+1)(k+2)+(k+1)(k+2)(k+3)P(k + 1) = 1 \cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + ... k(k + 1)(k + 2) + (k + 1)(k + 2)(k + 3) P(k+1)=k(k+1)(k+2)(k+3)4+(k+1)(k+2)(k+3)=(k+1)(k+2)(k+3)(k+4)4P(k + 1) = \frac{k(k+1)(k+2)(k+3)}{4} + (k+1)(k + 2)(k + 3) = \frac{(k + 1)(k + 2)(k + 3)(k + 4)}{4}

Which means that P(k+1)P(k + 1) is true and the induction step is verified.

Problem Sheet

Question 1

Prove that the sum of any even integers is even. In an other way show that:

n,mZ\forall n, m \in \mathbb{Z}, if nn and mm are even numbers then n+mn+m is also an even number.

Proof

Let n,mZn, m \in \mathbb{Z} and assume that nn and mm are even. We need to show that n + m is also even. n and m are two even integers, it follows by definition of even numbers that there exists 2 integers ii and jj such that n=2in = 2i and m=2jm = 2j. Thus, n+m=2i+2j=2(i+j)n + m = 2i + 2j = 2(i + j). Hence, there exists an integer k=i+jk = i + j such that n+m=2kn + m = 2k, it follows by definition of even numbers that n + m is even.

Question 2

Use direct proof to show that: n,mZ\forall n, m \in \mathbf{Z}, if nn is an even number and m is an odd number, then 3n + 2m is also an even number.

Proof

Let n,mZn, m \in \mathbb{Z} and assume that nn is an even number and mm is an odd number. We need to show that 3n + 2m is also an even number.

Assume that nn is even and mm is odd, this implies that there exists 2 integers i,jZi, j \in \mathbb{Z} such that: n=2in = 2i and m=2j+1m = 2j + 1.

Thus, 3n + 2m = 3(2i) + 2(2j + 1) = 2(3i) + 2(2j + 1) = 2(3i + 2j + 1)

Hence, there exists an integer k = (3i + 2j + 1) such that 3n + 2m = 2k.

By the definition of even numbers, we can see 3n + 2m number is even.

Question 3

Prove that the sum of any 2 odd integers is odd. In an other way show that: n,mZ\forall n, m \in \mathbb{Z} if nn and mm are odd numbers then n+mn + m is an even number.

Proof

Let n,mZn, m \in \mathbb{Z} and assume that nn is odd and mm is odd. We need to show that n+mn + m is even.

nn and mm are odd, which follows by definition of odd numbers that there exists 2 integers ii and jj such that n=2i+1n = 2i + 1 and m=2j+1m = 2j + 1

Thus, n+m=2i+1+2j+1=2i+2j+2=2(n+m+1)n + m = 2i + 1 + 2j + 1 = 2i + 2j + 2 = 2(n + m + 1)

Hence, there is an integer k=(n+m+1)k = (n + m + 1) such that n+m=2kn + m = 2k, which proves n+mn + m is even by the definition of even numbers.

Question 4

Show that for any odd number integer nn, n2n^2 is also odd.

In another way show that: nZ\forall n \in \mathbb{Z} if nn is odd then n2n^2 is odd.

Proof

Let nZn \in \mathbb{Z} and assume that nn is an odd number. We need to show that n2n^2 is also odd, which means show there's an integer kk such that n2=2k+1n^2 = 2k + 1.

By definition of odd, nn is odd which means there exists an integer ii such that n=2k+1n = 2k + 1.

It follows that n2=(2i+1)2=(2i+1)(2i+1)=4i2+4i+1=2(2i2+2i)+1n^2 = (2i+1)^2 = (2i + 1)(2i + 1) = 4i^2 + 4i + 1 = 2(2i^2 + 2i) + 1

2i2+2i2i^2 + 2i is an integer as it's the sum of products of integers.

Therefore, there exists k=2i2+2ik = 2i^2 + 2i such that n2=2k+1n^2 = 2k + 1.

It follows by definition of odd numbers that n2n^2 is an odd number.