Computer Science 789 Online Algorithms

Hint 3 for the Pascal Recursion Problem

Prove that the number of recursive calls is not more than 2 lg(n). Use strong induction.

Theoretically, you must consider all natural numbers n. But, in fact, n=0 can be disposed of by saying, "We can assume n > 0 by the input condition."

The other three cases are n=1, n > 1 even, and n > 1 odd.

Back to Course Page

Back to Assignment Page

Back to Assignment 1