Discrete-structures 08

Linear recurrence relation

The towers of Hanoi

At the time of the creation of the world, three high towers were created. 64 gold disks stacked on the leftmost tower. Each disk rested on a slightly larger disk. Buddhist monks were given the task to re-create the stack on the middle tower by moving disks, one at a time, to another tower with the rule that a larger disk could never be placed on top of a smaller disk. When the task will be completed, the world will end, and everybody will reach Nirvana. How many moves does it take to move the disks from tower to tower ?

Subsets of naturals

Tiling

Linear recurrence with constant coefficients definition

Solving homogeneous linear recurrence with constant coefficients

Characteristic polynomial of a recurrence relation definition

Root of characteristic polynomial form a basis lemma

Example

Example

Example

Example

Solving non-homogeneous linear recurrence with constant coefficients

---

Example