Back to all chapters
# Introduction to Recursion

The Fibonacci sequence is not the only one that is defined recursively. Learn how to solve combinatorics problems with recursion, and how to turn recurrence relations into closed-form expressions.

A toy model for a growing network is the recursive tree. The tree starts as a single node and at each step in the growth process, one new node is added which makes a single connection, at random, to an existing node.

Assume that the network has grown large enough so that its statistical properties are effectively constant. The fractions of nodes that have connections to exactly 7 other nodes is given by some fraction \(\dfrac ab\), where \(a\) and \(b\) are positive coprime integers. What is the value of \(a + b\)?

Consider a 9 layer pyramid, which comprises 45 people. Assuming that all the cheerleaders weigh 128 pounds each, and that the weight is equally distributed amongst both supporters, what is the most weight supported by anyone in this pyramid?

How would you generalize this?

Image credit: Wikipedia Pere Lopez

If we have a Tower of Hanoi with 42 pegs, and we have an additional rule that no disc can be moved more than twice, what is the maximum number of discs such that all discs can be moved to pegs other than the first peg \(P_1?\)

At \(t = 1\), all snowflakes which occupy the *exact* same points are merged into one, and then the process repeats for every snowflake, resulting in the following pattern:

So, to iterate the first few steps:

- There is \(1\) snowflake at time \(t = 0\)
- At time \(t = 1\), there are \(8\) snowflakes pre-merge.
- No snowflakes coincide, so there are \(8\) snowflakes post-merge as well.
- At time \(t = 2\), there are \(64\) snowflakes pre-merge.
- Post-merge, only \(33\) snowflakes remain.

How many snowflakes are there at time \(t = 1000\), post-merge?

×

Problem Loading...

Note Loading...

Set Loading...