search
Log In

Recent questions tagged discrete-mathematics

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 in Combinatory Lakshman Patel RJIT 128 views
0 votes
0 answers
12
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 in Combinatory Lakshman Patel RJIT 44 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 in Combinatory Lakshman Patel RJIT 31 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 in Combinatory Lakshman Patel RJIT 38 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 in Combinatory Lakshman Patel RJIT 27 views
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 in Combinatory Lakshman Patel RJIT 23 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 in Combinatory Lakshman Patel RJIT 27 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 in Combinatory Lakshman Patel RJIT 27 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 in Combinatory Lakshman Patel RJIT 22 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 in Combinatory Lakshman Patel RJIT 16 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 in Combinatory Lakshman Patel RJIT 16 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 in Combinatory Lakshman Patel RJIT 20 views
...