COMP 250 Study Guide - Midterm Guide: Memory Stick, Liquid Oxygen, Polynomial

• School: McGill University
• Department: Computer Science (Sci)
• Course: COMP 250
• Professor: Michael Langer

Document Summary

Recall the de nition of the nth fibonacci number fn: Thus, fib(6) is called one time, fib(5) one time, fib(4) two times, fib(3) three times, fib(2) ve times, and fib(1) eight times. Prove that your answer is correct by induction. In general, then, fib(m) is called fn m+1 times to calculate fn. We prove this by induction on n. base step: if n = 1 then m = 1 so fib(m) is called once which is equal to fn m+1 = f1 = 1. If n = 2 then fib(m=1) is called fn m+1 = f2 = 1 times and fib(m=2) is called. Fn m+1 = f1 = 1 times. induction step: assuming that fib(m) is called fk m+1 times when calculating fk and fk m times when calculating fk 1 for some constant k 2, we prove that fib(m) is called.