Help needed (Golden Ratio?)

man man

A staircase has n steps. A man climbs either one step or two steps at a time .Prove that the number of ways in which he can climb up the staircase , starting from the bottom , is

$\huge{\frac{1}{\sqrt{5}}[(\frac{ 1 + \sqrt{5}}{2})^{n + 1} - (\frac{ 1 - \sqrt{5}}{2})^{n + 1}]}$ $n \geq 1$

#Combinatorics #JEE

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

The answer is already mentioned, so I'll just express it algebraically.

Let $T_n$ be the number of steps required to climb a staircase with $n$ steps.

$T_1=1$

$T_2=2$

For $n\geq3$ , as @Michael Mendrin mentioned, we can start with one step, and the rest of it are $T_{n-1}$ steps. If we start on two steps, the rest of it are $T_{n-2}$ steps. Now we have a conclusion that

$T_n=T_{n-1}+T_{n-2}$

This is actually the Fibonacci Sequence, but we have to shift it to the right, since it starts with $1,2,...$ instead of the typical $1,1,2,...$ . Hence,

$T_n=F_{n+1}$

Christopher Boo - 6 years, 7 months ago

Thank you sir @Christopher Boo @Michael Mendrin @Aneesh Kundu @Siddhartha Srivastava @Agnishom Chattopadhyay

U Z - 6 years, 7 months ago

Well, let's see, let's say there's $a$ ways to climb up $n-2$ steps, and $b$ ways to climb up $n-1$ steps, so if we backtrack from the $n$ th step either $1$ or $2$ steps, then those would be the number of ways to get to those previous steps. Hence, the number of ways to get to the $n$ th step is $a+b$ , and we're looking at Fibonacci numbers. The formula give was a dead giveaway to the answer to this one. Thanks for the hint!

Addendum: If one wonders if starting at $n-2$ steps, there are actually $2$ ways to get to the $n$ th step, in fact the $1+1$ steps to the $n$ th step is already part of counting the ways up to and through the $n-1$ th step. So, it's still a string of honest Fibonacci numbers.

Michael Mendrin - 6 years, 7 months ago

The number of ways is just the fibonacci sequence. You can see this by noting the number of ways to climb n steps is equal to the number of ways where the second to last step gets you up n-2 steps, plus the number of ways where the second to last step gets you up n-1 steps. If s(n) represents the number of ways to climb up n steps, then it follows that s(n) + s(n+1) = s(n+2). Since s(1) = 1 and s(2) = 2 by inspection, this is just the fibonacci sequence shifted by 1, as expressed in the formula.

Rogers Epstein - 6 years, 7 months ago

We can notice that this looks similar to Binet’s Theorem, which is an explicit formula to give the nth number in the fibonacci sequence. In this case, it gives the (n+1)th term. The Fibonacci sequence is 1 1 2 3 5 8… while this sequence is 1 2 3 5 8… because the number of ways to get to each step adds up. This sequence is just the Fibonacci sequence with the first two terms as 1 and 2. QED

Jonathan Yang - 6 years, 7 months ago

@DEEPANSHU GUPTA @Sanjeet Raria @Sandeep Bhardwaj @Calvin Lin @Michael Mendrin @Pranjal Jain @Agnishom Chattopadhyay @Aditya Raut @Krishna Sharma

Please help

U Z - 6 years, 7 months ago

@Pranshu Gaba @Pranav Arora @Mursalin Habib

and others you too please help

U Z - 6 years, 7 months ago

As Christopher and Michael pointed out, you should have tried generating the first few terms of the series. You'll find it's a fibonacci series and if you are not familiar with the formula, look it up. :)

Agnishom Chattopadhyay - 6 years, 7 months ago

Where's n in that expression??

Pranjal Jain - 6 years, 7 months ago

O sorry thank you

U Z - 6 years, 7 months ago

Hint:- Use recurrence relations. Define $T_n$ as the number of ways to climb a staircase with $n$ steps. Shows its relation with $T_{n-1}$ and $T_{n-2}$ . You should come up with a familiar relation.

Siddhartha Srivastava - 6 years, 7 months ago

I think it has got something to do with Fibonacci numbers cause the expression gives the $n+1$ th Fibonacci number.

Aneesh Kundu - 6 years, 7 months ago

I encountered a similar question in the NMTC screening test this year.

Ronq Vader - 6 years, 7 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$