CSC 165 Computability, review

Week #12

Topic: computability, review

I really enjoyed learning about induction in a more sophisticated way. I always thought of induction as a process of going from a known case called base case to making generalizations that involve n and n+1 cases. The approach taken in class to prove statements by using the induction method made me fully understand how this method works.

I tried some somehow complex examples involving induction to reaffirm my knowledge.

Prove for all positive integers n, that 4ⁿ + 15n -1 is divisible by 9.

The first thing to notice in this exercise is that we are talking about positive integers which suggests that you should use induction to prove this statement.

As suggested in class, let’s start with the inductive step

Inductive Step

Assume 4ⁿ + 15n -1 is divisible by 9 # Induction hypothesis

We want show 4^{n + 1} + 15(n + 1) -1 is divisible by 9

4^{n + 1} + 15(n + 1) -1 = 4^{n + 1} + 15n + 15 -1

                                = 4^{n + 1} + 15n + 14

                                = (4^{n + 1} + 60n - 4) - 45n + 18           
                               # Manipulating the expression to use our induction hypothesis

                               ≡ 0 – 45n + 18 (mod 9)           # By induction hypothesis

                               ≡ 0 – 0 + 0         # 45n (mod 9) = 0 and 18 (mod 9) = 0

Since we did not notice any restriction on n, we can continue our induction process by establishing our base case.

Base Case

n = 1

4ⁿ + 15n -1 = 4⁽¹⁾ + 15(1) -1 = 18 ≡ 0(mod 9)

Another interesting induction problem is the following

Recall that {F_n}, the Fibonacci sequence, is defined by F₁ = 1, F₂ =1, and F_n = F_{n – 1} + F _{n – 2} . Let r be a positive constant that satisfies the property that r² = r + 1. Prove that  rⁿ = F_n r + F_{n – 1} .

Inductive Step

Assume rⁿ = F_n r + F_{n – 1} .     # Induction hypothesis

We want show r^{n + 1} = F_{n + 1} r + F_n

r^{n + 1} = rⁿ * r = (F_n r + F_{n – 1}) r         # By Induction hypothesis

          = (F_n r + F_{n +1} - F_n ) r # F_{n – 1}  = F_{n +1} - F_n

               = F_n r² + F_{n +1} r - F_n r

          = F_{n +1} r + (F_n r² - F_n r)

          = F_{n +1} r + (F_n (r² - r))

          = F_{n +1} r + F_n      # r² = r + 1

Here we notice that for the Fibonacci formula to work we need at least two elements. Therefore, we structure our base case as follows:

Base Case

n = 2

r² = F₂ r + F₁

r² = r + 1

Overall, it was a very good experience to do these SLOGS. Moreover, these posts helped me to reaffirm my knowledge and to increase my confidence when dealing with the material learned. Also, I really enjoyed learning all the topics taught in CSC165 and I hope that I will find more opportunities to apply math in Computer Science in upper years.