Discrete Structures208010 marksNumerical: solving recurrence relationPigeonhole Principle
State pigeonhole principle. Solve the recurrence relation an = 5an-1 - 6an-2, with initial conditions a1 = 1 and a2 = 3.
State pigeonhole principle. Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$, with initial conditions $a_1 = 1$ and $a_2 = 3$.[10]
- Recurrence: $an = 5a{n-1} - 6a{n-2}$ - Initial conditions: $a1 = 1$, $a2 = 3$ --- Statement: If $k+1$ or more objects are placed into $k$ boxes, then at least one box contains two or more objects. Generalized form: If $N$ objects are placed into $k$ boxes, then at least one box contains at leas...