search
Log In

Recent questions tagged kenneth-rosen

0 votes
2 answers
3
Suppose that there are $n = 2^{k}$ teams in an elimination tournament, where there are $\frac{n}{2}$ games in the first round, with the $\frac{n}{2} = 2^{k-1}$ winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.
asked May 10, 2020 in Combinatory Lakshman Patel RJIT 323 views
0 votes
1 answer
4
0 votes
1 answer
8
0 votes
1 answer
9
0 votes
1 answer
10
0 votes
0 answers
12
0 votes
0 answers
15
1 vote
0 answers
17
Prove Theorem $6:$Suppose that $\{a_{n}\}$ satisfies the liner nonhomogeneous recurrence relation $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k} + F(n),$ where $c_{1}.c_{2},\dots,c_{k}$ ... is $m,$ there is a particular solution of the form $n^{m}(p_{t}n^{t} + p_{t-1}n^{t-1} + \dots + p_{1}n + p_{0})s^{n}.$
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 104 views
0 votes
0 answers
18
Prove Theorem $4:$ Let $c_{1},c_{2},\dots,c_{k}$ be real numbers. Suppose that the characteristic equation $r^{k}-c_{1}r^{k-1}-\dots c_{k} = 0$ has $t$ distinct roots $r_{1},r_{2},\dots,r_{t}$ with multiplicities $m_{1},m_{2},\dots,m_{t},$ ... $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 94 views
0 votes
0 answers
19
Solve the recurrence relation $T (n) = nT^{2}(n/2)$ with initial condition $T (1) = 6$ when $n = 2^{k}$ for some integer $k.$ [Hint: Let $n = 2^{k}$ and then make the substitution $a_{k} = \log T (2^{k})$ to obtain a linear nonhomogeneous recurrence relation.]
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 84 views
2 votes
0 answers
20
It can be shown that Cn, the average number of comparisons made by the quick sort algorithm (described in preamble to question $50$ in exercise $5.4),$ when sorting $n$ ... $48$ to solve the recurrence relation in part $(A)$ to find an explicit formula for $C_{n}.$
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 65 views
0 votes
0 answers
21
0 votes
0 answers
22
Some linear recurrence relations that do not have constant coefficients can be systematically solved. This is the case for recurrence relations of the form $f (n)a_{n} = g(n)a_{n-1} + h(n).$ Exercises $48-50$ ... relation to obtain $a_{n} = \dfrac{C +\displaystyle{} \sum_{i = 1}^{n}Q(i)h(i)}{g(n + 1)Q(n + 1)}$
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 81 views
0 votes
0 answers
23
A new employee at an exciting new software company starts with a salary of $\$50,000$ and is promised that at the end of each year her salary will be double her salary of the previous year, with an extra increment of $\$10,000$ for each year she has been with the ... $n^{\text{th}}$ year of employment. Solve this recurrence relation to find her salary for her $n^{\text{th}}$ year of employment.
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 69 views
0 votes
0 answers
24
Suppose that there are two goats on an island initially.The number of goats on the island doubles every year by natural reproduction, and some goats are either added or removed each year. Construct a recurrence relation for the number of goats on the island at the start of the ... $n^{\text{th}}$ year for each $n \geq 3.$
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 94 views
0 votes
0 answers
25
Suppose that each pair of a genetically engineered species of rabbits left on an island produces two new pairs of rabbits at the age of $1$ month and six new pairs of rabbits at the age of $2$ months and every month afterward. None of the rabbits ever die or leave ... relation in $(A)$ determine the number of pairs of rabbits on the island $n$ months after one pair is left on the island.
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 68 views
0 votes
0 answers
26
(Linear algebra required ) Let $A_{n}$ be the $n \times n$ matrix with $2s$ on its main diagonal, $1s$ in all positions next to a diagonal element, and $0s$ everywhere else. Find a recurrence relation for $d_{n},$ the determinant of $A_{n}.$ Solve this recurrence relation to find a formula for $d_{n}.$
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 58 views
0 votes
0 answers
27
Express the solution of the linear nonhomogenous recurrence relation $a_{n} = a_{n-1} + a_{n-2} + 1\:\text{for}\: n \geq 2 \:\text{where}\: a_{0} = 0\:\text{and}\: a_{1} = 1$ in terms of the Fibonacci numbers. [Hint: Let $b_{n} = a_{n + 1}$ and apply question $42$ to the sequence $b_{n}.]$
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 39 views
0 votes
0 answers
28
0 votes
0 answers
29
Use the formula found in Example $4$ for $f_{n},$ the $n^{\text{th}}$ Fibonacci number, to show that fn is the integer closest to $\dfrac{1}{\sqrt{5}}\left(\dfrac{1 + \sqrt{5}}{2}\right)^{n}$ Determine for which $n\: f_{n}$ ... $n\: f_{n}$ is less than $\dfrac{1}{\sqrt{5}}\left(\dfrac{1 + \sqrt{5}}{2}\right)^{n}.$
asked May 6, 2020 in Combinatory Lakshman Patel RJIT 45 views
0 votes
1 answer
30
...