4
$\begingroup$

This question already has an answer here:

"Sarah", I said, "Have I ever told you about the times in my childhood when I'd go down to Infinity Creek?". "No", she replied, "but it sounds interesting".

"When I was a boy, I lived next to a creek. This wasn't any ordinary creek - it stretched on for what seems like forever. In fact, this is why we called it Infinity Creek. It just so happened that there was a single line of stepping stones, going from one bank to the other, over thousands and thousands of kilometers."

"I would always wonder about how many ways I could cross that creek. You see, I was athletic and could choose to jump two stones at a time, instead of just one."

Sarah looked at me. "I don't understand".

"Well, imagine I had a creek with three stepping stones.", I replied. "I could jumped them all one by one, I could jump over the first one then jump all the rest one by one - the list goes on. Here's a diagram..."

I scribbled a rough sketch in the dirt.

why do birds suddenly appear

"As you can see, I would have five ways to cross a creek with 3 stepping stones."

Sarah nodded in understanding. "So you wanted to know..."

"...how many ways I could cross Infinity Creek. Yes."

Sarah looked puzzled. "But you didn't know how many stones there were?"

"Oh yes, I did know", I replied. "There were $42^{25}$ stones. Perhaps now, a bit more mathematically minded, I could work out how many ways I could have crossed Infinity Creek. But because I suspect it is a large number, I would be happy with just the natural log of the number, rounded to the nearest whole value."

Can you help me?

Note: This does not require any large amounts of processing power!

$\endgroup$

marked as duplicate by Joe Z., mmking, Julian Rosen, Doorknob Jun 20 '15 at 3:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

I've seen this problem before. The number of ways you could jump $n$ steps is equal to the number of ways you could jump $n-1$ steps (your last jump is from the last stone) plus the number of ways you could jump $n-2$ steps (if your last jump skips a stone).

This is, of course, equal to the $n+2$th Fibonacci number, if the first two are 1 and 1. So the natural log of the path number for $42^{25}$ stepping stones would be very very close to $42^{25} \log \phi - \log \sqrt 5$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.