You are currently browsing the category archive for the
‘Combinatorics’ category. Sometimes sequences of numbers are
defined recursively, so that given the previous terms of the
sequence we can find the next term. A classic example of this is
the sequence of Fibonacci numbers, where every two consecutive
terms determine the next term, and so if we are given the first
two terms, we can calculate the whole sequence. However, if we
wanted to, say, calculated the 1000th Fibonacci number, we’d
have to start out with the first two, add them to compute the
3rd, add the second and third to compute the 4th, and so on, to
slowly build up every single Fibonacci number before the 1000th
in order to get there. It’d be much nicer if we had a formula
for the Fibonacci sequence. That way, if we wanted the 1000th
Fibonacci number, all we’d have to do is plug 1000 into the
formula to compute it. Of course, the formula is only useful if
it takes less time to crunch it out than it does to do it the
brute-force way. A method of f