The Gateway to Computer Science Excellence
+2 votes

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.
in Algorithms by | 131 views

1 Answer

+2 votes
Best answer
(a). Suppose we need to reach the $n^{th}$ step , we can reach so from the $n-1^{th}$ step or from the $n-2^{th}$ step.

Let $a_n$ be the number of ways we can reach the $n^{th}$ step.

Therefore $a_n=a_{n-1}+a_{n-2}$ which follows from my initial statement.

(b) $a_0=0,a_1=1$. Trivially .

(c). The characteristic equation of the recurrence relation is of the form : $r^2-r-1=0$. The roots are $1+\frac{\sqrt{5}}{2}$,$1-\frac{\sqrt{5}}{2}$. Therefore closed form solution of the recurrence relation is : $a_n$=$\alpha_{0}(1+\frac{\sqrt{5}}{2})^{n}$ + $\alpha_{1}(1-\frac{\sqrt{5}}{2})^{n}$

$\because$ $a_0$=0. We have 0=$\alpha_0+\alpha_1$ $\implies$ $\alpha_0=-\alpha_1$.

$a_1$=$\alpha_{0}(1+\frac{\sqrt{5}}{2})$ + $\alpha_{1}(1-\frac{\sqrt{5}}{2})$ $\implies$$a_1$=$-\alpha_{1}(1+\frac{\sqrt{5}}{2})$ + $\alpha_{1}(1-\frac{\sqrt{5}}{2})$ $\implies$ $a_1=-2 \times \frac{\sqrt{5}}{2}\alpha_1$=$-\sqrt{5}\alpha_1$

$\because a_1=1 \therefore \alpha_1$=$-\frac{1}{\sqrt{5}} \implies  \alpha_0= \frac{1}{\sqrt{5}}$

$\therefore a_n=\frac{1}{\sqrt{5}}(1+\frac{\sqrt{5}}{2})^n-\frac{1}{\sqrt{5}}(1-\frac{\sqrt{5}}{2})^n$
selected by

give explanation otherwise make it as comment @Arkaprava

Answer updated.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,497 answers
95,315 users