Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged recurrence-relation
0
votes
1
answer
151
Kenneth Rosen Edition 7 Exercise 8.2 Question 18 (Page No. 525)
Solve the recurrence relation $a_{n} = 6a_{n−1} − 12a_{n−2} + 8a_{n−3} \:\text{with}\: a_{0} = −5, a_{1} = 4,\: \text{and}\: a_{2} = 88.$
Solve the recurrence relation $a_{n} = 6a_{n−1} − 12a_{n−2} + 8a_{n−3} \:\text{with}\: a_{0} = −5, a_{1} = 4,\: \text{and}\: a_{2} = 88.$
admin
249
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
152
Kenneth Rosen Edition 7 Exercise 8.2 Question 17 (Page No. 525)
Prove this identity relating the Fibonacci numbers and the binomial coefficients: $f_{n+1} = C(n, 0) + C(n − 1, 1) +·\dots+ C(n − k, k),$ where $n$ is a positive integer and $k = n/2 .$ ... Show that the sequence $\{a_{n}\}$ satisfies the same recurrence relation and initial conditions satisfied by the sequence of Fibonacci numbers.]
Prove this identity relating the Fibonacci numbers and the binomial coefficients: $f_{n+1} = C(n, 0) + C(n − 1, 1) +·\dots+ C(n − k, k),$ where $n$ is a positive int...
admin
207
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
153
Kenneth Rosen Edition 7 Exercise 8.2 Question 16 (Page No. 525)
Prove Theorem $3:$ 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 $k$ distinct roots $r_{1},r_{2},\dots r_{k}.$ Then a sequence $\{a_{n}\}$ ... $n = 0,1,2,\dots,$ where $\alpha_{1},\alpha_{2},\dots,\alpha_{k}$ are constants.
Prove Theorem $3:$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 $k$ distinct roots...
admin
219
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
154
Kenneth Rosen Edition 7 Exercise 8.2 Question 15 (Page No. 525)
Find the solution to $a_{n} = 2a_{n−1} + 5a_{n−2} − 6a_{n−3}\: \text{with}\: a_{0} = 7, a_{1} = −4,\:\text{and}\: a_{2} = 8.$
Find the solution to $a_{n} = 2a_{n−1} + 5a_{n−2} − 6a_{n−3}\: \text{with}\: a_{0} = 7, a_{1} = −4,\:\text{and}\: a_{2} = 8.$
admin
237
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
155
Kenneth Rosen Edition 7 Exercise 8.2 Question 14 (Page No. 525)
Find the solution to $a_{n} = 5a_{n−2}− 4a_{n−4} \:\text{with}\: a_{0} = 3, a_{1} = 2, a_{2} = 6, \:\text{and}\: a_{3} = 8.$
Find the solution to $a_{n} = 5a_{n−2}− 4a_{n−4} \:\text{with}\: a_{0} = 3, a_{1} = 2, a_{2} = 6, \:\text{and}\: a_{3} = 8.$
admin
212
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
156
Kenneth Rosen Edition 7 Exercise 8.2 Question 13 (Page No. 525)
Find the solution to $a_{n} = 7a_{n−2} + 6a_{n−3}\:\text{with}\: a_{0} = 9, a_{1} = 10, \text{and}\: a_{2} = 32.$
Find the solution to $a_{n} = 7a_{n−2} + 6a_{n−3}\:\text{with}\: a_{0} = 9, a_{1} = 10, \text{and}\: a_{2} = 32.$
admin
220
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
157
Kenneth Rosen Edition 7 Exercise 8.2 Question 12 (Page No. 525)
Find the solution to $a_{n} = 2a_{n−1} + a_{n−2} − 2a_{n−3} \:\text{for}\: n = 3, 4, 5,\dots, \:\text{with}\: a_{0} = 3, a_{1} = 6, \:\text{and}\: a_{2} = 0.$
Find the solution to $a_{n} = 2a_{n−1} + a_{n−2} − 2a_{n−3} \:\text{for}\: n = 3, 4, 5,\dots, \:\text{with}\: a_{0} = 3, a_{1} = 6, \:\text{and}\: a_{2} = 0.$
admin
231
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
158
Kenneth Rosen Edition 7 Exercise 8.2 Question 11 (Page No. 525)
The Lucas numbers satisfy the recurrence relation $L_{n} = L_{n−1} + L_{n−2},$ and the initial conditions $L_{0} = 2$ and $L_{1} = 1.$ Show that $L_{n} = f_{n−1} + f_{n+1}\: \text{for}\: n = 2, 3,\dots,$ where fn is the $n^{\text{th}}$ Fibonacci number. Find an explicit formula for the Lucas numbers.
The Lucas numbers satisfy the recurrence relation $L_{n} = L_{n−1} + L_{n−2},$ and the initial conditions $L_{0} = 2$ and $L_{1} = 1.$ Show that $L_{n} = f_{n−1} + ...
admin
234
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
159
Kenneth Rosen Edition 7 Exercise 8.2 Question 10 (Page No. 525)
Prove Theorem $2:$ Let $c_{1}$ and $c_{2}$ be real numbers with $c_{2}\neq 0.$ Suppose that $r^{2}-c_{1}r-c_{2} = 0$ has only one root $r_{0}.$ A sequence $\{a_{n}\}$ ... $n = 0,1,2,\dots,$ where $\alpha_{1}$ and $\alpha_{2}$ are constants.
Prove Theorem $2:$ Let $c_{1}$ and $c_{2}$ be real numbers with $c_{2}\neq 0.$ Suppose that $r^{2}-c_{1}r-c_{2} = 0$ has only one root $r_{0}.$ A sequence $\{a_{n}\}$ is ...
admin
224
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
proof
+
–
0
votes
0
answers
160
Kenneth Rosen Edition 7 Exercise 8.2 Question 9 (Page No. 525)
A deposit of $\$100,000$ is made to an investment fund at the beginning of a year. On the last day of each year two dividends are awarded. The first dividend is $ ... $n$ years if no money has been withdrawn?
A deposit of $\$100,000$ is made to an investment fund at the beginning of a year. On the last day of each year two dividends are awarded. The first dividend is $20\%$ of...
admin
542
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
161
Kenneth Rosen Edition 7 Exercise 8.2 Question 8 (Page No. 524 - 525)
A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years. Find a recurrence relation for $\{L_{n}\},$ ... if $100,000$ lobsters were caught in year $1\:\text{ and}\: 300,000$ were caught in year $2.$
A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two ...
admin
324
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
162
Kenneth Rosen Edition 7 Exercise 8.2 Question 7 (Page No. 524)
In how many ways can a $2 \times n$ rectangular checkerboard be tiled using $1 \times 2 \:\text{and}\: 2 \times 2$ pieces?
In how many ways can a $2 \times n$ rectangular checkerboard be tiled using $1 \times 2 \:\text{and}\: 2 \times 2$ pieces?
admin
281
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
163
Kenneth Rosen Edition 7 Exercise 8.2 Question 6 (Page No. 524)
How many different messages can be transmitted in $n$ microseconds using three different signals if one signal requires $1$ microsecond for transmittal, the other two signals require $2$ microseconds each for transmittal, and a signal in a message is followed immediately by the next signal?
How many different messages can be transmitted in $n$ microseconds using three different signals if one signal requires $1$ microsecond for transmittal, the other two sig...
admin
369
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
164
Kenneth Rosen Edition 7 Exercise 8.2 Question 5 (Page No. 524)
How many different messages can be transmitted in $n$ microseconds using the two signals described in question $19$ in Section $8.1?$
How many different messages can be transmitted in $n$ microseconds using the two signals described in question $19$ in Section $8.1?$
admin
262
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
165
Kenneth Rosen Edition 7 Exercise 8.2 Question 4 (Page No. 524)
Solve these recurrence relations together with the initial conditions given. $a_{n} = a_{n-1}+ 6a_{n-2} \:\text{for}\: n \geq 2, a_{0} = 3, a_{1} = 6$ $a_{n} = 7a_{n-1}− 10a_{n-2} \:\text{for}\: n \geq 2, a_{0} = 2, a_{1} = 1$ ... $a_{n+2} = −4a_{n+1} + 5a_{n} \:\text{for}\: n \geq 0, a_{0} = 2, a_{1} = 8$
Solve these recurrence relations together with the initial conditions given.$a_{n} = a_{n-1}+ 6a_{n-2} \:\text{for}\: n \geq 2, a_{0} = 3, a_{1} = 6$$a_{n} = 7a_{n-1}− ...
admin
360
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
166
Kenneth Rosen Edition 7 Exercise 8.2 Question 3 (Page No. 524)
Solve these recurrence relations together with the initial conditions given. $a_{n} = 2a_{n−1}\:\text{for}\: n \geq 1, a_{0} = 3$ $a_{n} = a_{n−1} \:\text{for}\: n \geq 1, a_{0} = 2$ ... $a_{n} = a_{n−2} /4 \:\text{for}\: n \geq 2, a_{0} = 1, a_{1} = 0$
Solve these recurrence relations together with the initial conditions given.$a_{n} = 2a_{n−1}\:\text{for}\: n \geq 1, a_{0} = 3$ $a_{n} = a_{n−1} \:\text{for}\: n \ge...
admin
1.1k
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
167
Kenneth Rosen Edition 7 Exercise 8.2 Question 2 (Page No. 524)
Determine which of these are linear homogeneous recurrence relations with constant coefficients. Also, find the degree of those that are. $a_{n} = 3a_{n-2}$ $a_{n} = 3$ $a_{n} = a^{2}_{n−1}$ $an = a_{n−1} + 2a_{n−3}$ $an = a_{n−1}/n$ $an = a_{n−1} + a_{n−2} + n + 3$ $a_{n} = 4a_{n−2} + 5a_{n−4} + 9a_{n−7}$
Determine which of these are linear homogeneous recurrence relations with constant coefficients. Also, find the degree of those that are.$a_{n} = 3a_{n-2}$ $a_{n} = 3$ $a...
admin
707
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
168
Kenneth Rosen Edition 7 Exercise 8.2 Question 1 (Page No. 524)
Determine which of these are linear homogeneous recurrence relations with constant coefficients. Also, find the degree of those that are. $a_{n} = 3a_{n−1} + 4a_{n−2} + 5a_{n−3}$ $a_{n} = 2na_{n−1} + a_{n−2}$ $a_{n} = a_{n−1} + a_{n−4}$ $a_{n} = a_{n−1} + 2 $ $a_{n} = a^{2}_{n−1} + a_{n−2} $ $a_{n} = a_{n−2}$ $a_{n} = a_{n−1} + n$
Determine which of these are linear homogeneous recurrence relations with constant coefficients. Also, find the degree of those that are.$a_{n} = 3a_{n−1} + 4a_{n−2} ...
admin
4.5k
views
admin
asked
May 3, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
169
NIELIT 2017 OCT Scientific Assistant A (IT) - Section B: 14
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by$T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$Where $p,q$ are constan...
admin
860
views
admin
asked
Apr 1, 2020
Algorithms
nielit2017oct-assistanta-it
algorithms
recurrence-relation
time-complexity
master-theorem
+
–
0
votes
1
answer
170
NIELIT 2017 OCT Scientific Assistant A (IT) - Section B: 34
The solution of the recurrence relation $a_{r} = a_{r-1} + 2a_{r-2}$ with $a_{0} = 2,a_{1} = 7$ is $a_{r} = (3)^{r} + (1)^{r}$ $2a_{r} = (2)^{r}/3 – (1)^{r}$ $a_{r} = 3^{r+1} – (-1)^{r}$ $a_{r} = 3(2)^{r} – (-1)^{r}$
The solution of the recurrence relation$a_{r} = a_{r-1} + 2a_{r-2}$ with $a_{0} = 2,a_{1} = 7$ is$a_{r} = (3)^{r} + (1)^{r}$$2a_{r} = (2)^{r}/3 – (1)^{r}$$a_{r} = 3^{r+...
admin
683
views
admin
asked
Apr 1, 2020
Combinatory
nielit2017oct-assistanta-it
combinatory
recurrence-relation
+
–
1
votes
1
answer
171
NIELIT 2017 OCT Scientific Assistant A (CS) - Section C: 4
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by $T(n) = 8T(n/2) + qn,$ if $n>1$ $ = p,$ if $n = 1$ Where $p,q$ are constants. The order of this algorithm is $n^{2}$ $n^{n}$ $n^{3}$ $n$
The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by$T(n) = 8T(n/2) + qn,$ if $n>1$$ = p,$ if $n = 1$Where $p,q$ are constants. The or...
admin
1.3k
views
admin
asked
Apr 1, 2020
Algorithms
nielit2017oct-assistanta-cs
algorithms
recurrence-relation
time-complexity
master-theorem
+
–
1
votes
1
answer
172
NIELIT 2017 OCT Scientific Assistant A (CS) - Section C: 6
The solution of the recurrence relation $a_{r} = a_{r-1} + 2a_{r-2}$ with $a_{0} = 2,a_{1} = 7$ is $a_{r} = (3)^{r} + (1)^{r}$ $2a_{r} = (2)^{r}/3 – (1)^{r}$ $a_{r} = 3^{r+1} – (-1)^{r}$ $a_{r} = 3(2)^{r} – (-1)^{r}$
The solution of the recurrence relation$a_{r} = a_{r-1} + 2a_{r-2}$ with $a_{0} = 2,a_{1} = 7$ is$a_{r} = (3)^{r} + (1)^{r}$$2a_{r} = (2)^{r}/3 – (1)^{r}$$a_{r} = 3^{r+...
admin
472
views
admin
asked
Apr 1, 2020
Combinatory
nielit2017oct-assistanta-cs
discrete-mathematics
combinatory
recurrence-relation
+
–
1
votes
2
answers
173
NIELIT 2016 MAR Scientist B - Section C: 22
Time complexity of an algorithm $T(n)$, where $n$ is the input size is given by $\begin{array}{ll}T(n) & =T(n-1)+\frac{1}{n}, \text{ if }n>1\\ & =1, \text{ otherwise} \end{array}$ The order of this algorithm is $\log n$ $n$ $n^2$ $n^n$
Time complexity of an algorithm $T(n)$, where $n$ is the input size is given by$\begin{array}{ll}T(n) & =T(n-1)+\frac{1}{n}, \text{ if }n>1\\ & =1, \text{ otherwise} \en...
admin
1.4k
views
admin
asked
Mar 31, 2020
Algorithms
nielit2016mar-scientistb
algorithms
recurrence-relation
time-complexity
+
–
2
votes
1
answer
174
NIELIT 2016 DEC Scientist B (IT) - Section B: 16
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is: $T(n)=2T(n-2)+2$ $T(n)=2T(n/2)+1$ $T(n)=2T(n-1)+n$ $T(n)=2T(n-1)+1$
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is:$T(n)=2T(n-2)+2$$T(n)=2T(n/2)+1$$T(n)=2T(n-1)+n$$T(n)=2T(n-1...
admin
2.4k
views
admin
asked
Mar 31, 2020
DS
nielit2016dec-scientistb-it
data-structures
recurrence-relation
+
–
1
votes
1
answer
175
NIELIT 2016 DEC Scientist B (CS) - Section B: 27
What is the solution to the recurrence $T(n)=T \bigg (\dfrac{n}{2} \bigg )+n$? $O(\log n)$ $O(n)$ $O(n\log n)$ None of these
What is the solution to the recurrence $T(n)=T \bigg (\dfrac{n}{2} \bigg )+n$?$O(\log n)$$O(n)$$O(n\log n)$None of these
admin
1.1k
views
admin
asked
Mar 31, 2020
Algorithms
nielit2016dec-scientistb-cs
algorithms
recurrence-relation
time-complexity
+
–
1
votes
1
answer
176
NIELIT 2017 July Scientist B (CS) - Section B: 55
Suppose $T(n)=2T(n/2)+n$, $T(0)=T(1)=1$ which one of the following is false? $T(n)=O(n^2)$ $T(n)=\Theta(n\log n)$ $T(n)=\Omega(n^2)$ $T(n)=O(n\log n)$
Suppose $T(n)=2T(n/2)+n$, $T(0)=T(1)=1$ which one of the following is false?$T(n)=O(n^2)$$T(n)=\Theta(n\log n)$$T(n)=\Omega(n^2)$$T(n)=O(n\log n)$
admin
871
views
admin
asked
Mar 30, 2020
Algorithms
nielit2017july-scientistb-cs
algorithms
recurrence-relation
+
–
34
votes
4
answers
177
GATE CSE 2020 | Question: 2
For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is $\Theta (\log_a \log _b n)$ $\Theta (\log_{ab} n$) $\Theta (\log_{b} \log_{a} \: n$) $\Theta (\log_{2} \log_{2} n$)
For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is$\Theta (\log_a \log _b n)$ $\Theta (\log_{ab} n$)$\Thet...
Arjun
19.3k
views
Arjun
asked
Feb 12, 2020
Algorithms
gatecse-2020
algorithms
recurrence-relation
1-mark
+
–
2
votes
2
answers
178
ISI2015-MMA-1
Let $\{f_n(x)\}$ be a sequence of polynomials defined inductively as $ f_1(x)=(x-2)^2$ $f_{n+1}(x) = (f_n(x)-2)^2, \: \: \: n \geq 1$ Let $a_n$ and $b_n$ respectively denote the constant term and the coefficient of $x$ in $f_n(x)$. Then $a_n=4, \: b_n=-4^n$ $a_n=4, \: b_n=-4n^2$ $a_n=4^{(n-1)!}, \: b_n=-4^n$ $a_n=4^{(n-1)!}, \: b_n=-4n^2$
Let $\{f_n(x)\}$ be a sequence of polynomials defined inductively as$$ f_1(x)=(x-2)^2$$$$f_{n+1}(x) = (f_n(x)-2)^2, \: \: \: n \geq 1$$Let $a_n$ and $b_n$ respectively de...
Arjun
1.2k
views
Arjun
asked
Sep 23, 2019
Combinatory
isi2015-mma
recurrence-relation
non-gate
+
–
0
votes
1
answer
179
IIIT BLR TEST 1 : ALGORITHMS 1
Solve the following recursions ( in terms of Θ ). T(0) = T(1) = Θ(1) in all of the following. $T(n) = n + \frac{1}{n}\sum_{i=0}^{i=n-1}T(i)$ $T(n) = n + \frac{2}{n}\sum_{i=0}^{i=n-1}T(i)$ $T(n) = n + \frac{4}{n}\sum_{i=0}^{i=n/2}T(i)$ $T(n) = n + \frac{40}{n}\sum_{i=0}^{i=n/5}T(i)$
Solve the following recursions ( in terms of Θ ).T(0) = T(1) = Θ(1) in all of the following.$T(n) = n + \frac{1}{n}\sum_{i=0}^{i=n-1}T(i)$$T(n) = n + ...
Shaik Masthan
797
views
Shaik Masthan
asked
Aug 27, 2019
Algorithms
iiit-blr
algorithms
time-complexity
recurrence-relation
+
–
0
votes
0
answers
180
Cormen Edition 3 Exercise 7.4 Question 1 (Page No. 184)
Show that in the recurrence $T(n)=\max_{0<q\leq n-1} (T(q)+T(n-q-1))+\Theta(n)$ $T(n)=\Omega(n^2)$
Show that in the recurrence$T(n)=\max_{0<q\leq n-1} (T(q)+T(n-q-1))+\Theta(n)$$T(n)=\Omega(n^2)$
akash.dinkar12
324
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
recurrence-relation
descriptive
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
...
24
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register