A) find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one stair or two stairs at a time. b) what are the initial conditions? c) in how many ways can this person climb a flight of eight stairs?

a)

b) a₁ = 1, a₂ = 2

3) a₈ = 34

Where aₙ counts the total ways to climb n stairs.

Step-by-step explanation:

We can obtain the total number of possibilities to climb n stairs by using a recurrence relation. Since you can take 1 or 2 stairs at the time, it would be logical to use two initial conditions. Lets call an the total number of possibilities to climb n stairs. We have:

To climb 1 stair, we have only 1 possibility.

To climb 2 stairs we have 2 possibilities, taking the 2 at the same time, or taking one at the time.

If n is eqaual or greater than 1, then n+2 will be equal or greater than 3, and we should be able to deduce an+2 from an and an+1. First, we have 2 possibilities: we climb 1 stair and then climb n+1, or we climb 2 stairs at the same time and then climb n. Since we have to pick one option, we obtain that the total amount of possibilities to climb n+2 stairs is the sum of an+1 with an. Therefore

a)

b) We obtained this before, ,

c) Lets calculate each term

a₁ = 1

a₂ = 2

a₃ = a₁+a₂ = 3

a₄ = a₃+a₂ = 3+2 = 5

a₅ = 5+3 = 8

a₆ = 8+5 = 13

a₇ = 13+8 = 21

a₈ = 21+13 = 34

Thus, there are 34 ways to climb 8 stairs.

a is the correct