Find the number of ways to climb an n-stair staircase if each step allowed is either one or two stairs. So for example, a 3-stair staircase can be climbed in three different ways, namely 1-1-1 or 2-1 or 1-2. Verify that your formula is correct by mathematical induction.