Find an explicit formula for the sequence of exercise 39

Chapter 5, Problem 17E

(choose chapter or problem)

Problem 17E

Find an explicit formula for the sequence of exercise 39 in Section 5.6

Reference:

With each step you take when climbing a staircase, you can move up either one stair or two stairs. As a result, you can climb the entire staircase taking one stair at a time, taking two at a time, or taking a combination of one- and two-stair increments. For each integer n ≥ 1, if the staircase consists of n stairs, let cn be the number of different ways to climb the staircase. Find a recurrence relation for c1, c2, c3, . . . .