An important technique in mathematics is proof by induction. We start a proof by induction by proving that if something is true for one number, then it must be true for the next number also. In other words, if what we are trying to prove is true for n, then it must be true for n+1 . This is called the inductive step in the proof. Next, we show that it is true for the number 1. This is called the base step in the proof. Putting the base step and the inductive step together, we can then see that the item in question must be true for all positive integers because if it is true for 1, then it must be true for 1 +1, then for 2+1, then 3+1 , and so on. How is a proof by induction similar to conditional linear recursion?