ISI 2019 | PCB CS | Question: 12

Question

You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time.

1. Formulate a recurrence relation for counting $a_{n},$ the number of distinct ways in which you can climb up the staircase.
2. Mention the boundary conditions for your recurrence relation.
3. Find a closed form expression for $a_{n}$ by solving your recurrence.

Answer 1

Let $a_n$ be the number of ways to get at $n^{th}$ step.

For $n^{th}$ step, there are two possible cases -

Case $1$ : We got at $n^{th}$ step by taking step of $1$ from $(n-1)^{th}$ step.

$\therefore$ number of ways = $a_{n-1}$.

Case $2$ : We got at $n^{th}$ step by taking step of $2$ from $(n-2)^{th}$ step.

$\therefore$ number of ways = $a_{n-2}$.

$\therefore$ Recurrence relation is $a_n = a_{n-1} + a_{n-2}$.

Base Case -

$a_1 = 1, a_2 = 2$.

Since, there is $1$ way to get to $1^{st}$ step ie take step of $1$ and there is $2$ ways to get to $2^{nd}$ step ie take step of $1$ followed by another step of $1$ or take step of $2$.

We have, $a_n = a_{n-1} + a_{n-2} \implies a_n - a_{n-1} - a_{n-2} = 0$.

$\therefore$ characteristics equation is $r^n - r^{n-1} - r^{n-2} = 0$.

$\therefore r^2 - r - 1 = 0 \implies r = \frac{1\pm \sqrt{1+4}}{2}$

$\therefore \lambda_{1} = \frac{1+\sqrt5}{2}, \lambda_2 = \frac{1-\sqrt5}{2}$.

And $a_n = c_1\lambda_1^n + c_2\lambda_2^n$.

Solving for $c_1 \text{ and } c_2$ we get -

$c_1 = \frac{1+\frac{1}{\sqrt5}}{2} \text{ and } c_2 = \frac{1-\frac{1}{\sqrt5}}{2}$.

$\therefore a_n = \left(\frac{1+\frac{1}{\sqrt5}}{2}\right) * \left(\frac{1+\sqrt5}{2}\right)^n + \left(\frac{1-\frac{1}{\sqrt5}}{2}\right) * \left(\frac{1+\sqrt5}{2}\right)^n$.