Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged descriptive
0
votes
1
answer
181
Kenneth Rosen Edition 7 Exercise 8.3 Question 10 (Page No. 535)
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
Find $f (n)$ when $n = 2^{k},$ where $f$ satisfies the recurrence relation $f (n) = f (n/2) + 1 \:\text{with}\: f (1) = 1.$
admin
375
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
182
Kenneth Rosen Edition 7 Exercise 8.3 Question 9 (Page No. 535)
Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find $f (5)$ $f (125)$ $f (3125)$
Suppose that $f (n) = f (n/5) + 3n^{2}$ when $n$ is a positive integer divisible by $5, \:\text{and}\: f (1) = 4.$ Find$f (5)$$f (125)$$f (3125)$
admin
397
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
183
Kenneth Rosen Edition 7 Exercise 8.3 Question 8 (Page No. 535)
Suppose that $f (n) = 2f (n/2) + 3$ when $n$ is an even positive integer, and $f (1) = 5.$ Find $f (2)$ $f (8)$ $f (64)$ $(1024)$
Suppose that $f (n) = 2f (n/2) + 3$ when $n$ is an even positive integer, and $f (1) = 5.$ Find$f (2)$$f (8)$$f (64)$$(1024)$
admin
730
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
184
Kenneth Rosen Edition 7 Exercise 8.3 Question 7 (Page No. 535)
Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find $f (3)$ $f (27)$ $f (729)$
Suppose that $f (n) = f (n/3) + 1$ when $n$ is a positive integer divisible by $3,$ and $f (1) = 1.$ Find$f (3)$$f (27)$$f (729)$
admin
500
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
185
Kenneth Rosen Edition 7 Exercise 8.3 Question 6 (Page No. 535)
How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example $5?$
How many operations are needed to multiply two $32 \times 32$ matrices using the algorithm referred to in Example $5?$
admin
356
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
186
Kenneth Rosen Edition 7 Exercise 8.3 Question 5 (Page No. 535)
Determine a value for the constant C in Example $4$ and use it to estimate the number of bit operations needed to multiply two $64$-bit integers using the fast multiplication algorithm.
Determine a value for the constant C in Example $4$ and use it to estimate the number of bit operations needed to multiply two $64$-bit integers using the fast multiplica...
admin
266
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
187
Kenneth Rosen Edition 7 Exercise 8.3 Question 4 (Page No. 535)
Express the fast multiplication algorithm in pseudocode.
Express the fast multiplication algorithm in pseudocode.
admin
373
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
188
Kenneth Rosen Edition 7 Exercise 8.3 Question 3 (Page No. 535)
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.
Multiply $(1110)_{2} \:\text{and}\: (1010)_{2}$ using the fast multiplication algorithm.
admin
337
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
189
Kenneth Rosen Edition 7 Exercise 8.3 Question 2 (Page No. 535)
How many comparisons are needed to locate the maximum and minimum elements in a sequence with $128$ elements using the algorithm in Example $2$?
How many comparisons are needed to locate the maximum and minimum elements in a sequence with $128$ elements using the algorithm in Example $2$?
admin
358
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
190
Kenneth Rosen Edition 7 Exercise 8.3 Question 1 (Page No. 535)
How many comparisons are needed for a binary search in a set of $64$ elements?
How many comparisons are needed for a binary search in a set of $64$ elements?
admin
435
views
admin
asked
May 9, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
1
votes
0
answers
191
Kenneth Rosen Edition 7 Exercise 8.2 Question 52 (Page No. 527)
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}$ ... solution of the form $n^{m}(p_{t}n^{t} + p_{t-1}n^{t-1} + \dots + p_{1}n + p_{0})s^{n}.$
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),$$ w...
admin
388
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
192
Kenneth Rosen Edition 7 Exercise 8.2 Question 51 (Page No. 527)
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}$ ... $\alpha_{i,j}$ are constants for $1 \leq i \leq t\:\text{and}\: 0 \leq j \leq m_{i} - 1.$
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_...
admin
363
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
193
Kenneth Rosen Edition 7 Exercise 8.2 Question 53 (Page No. 527)
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.]
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 sub...
admin
411
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
2
votes
0
answers
194
Kenneth Rosen Edition 7 Exercise 8.2 Question 50 (Page No. 527)
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}.$
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$ e...
admin
260
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
195
Kenneth Rosen Edition 7 Exercise 8.2 Question 49 (Page No. 527)
Use question $48$ to solve the recurrence relation $(n + 1)a_{n} = (n + 3)a_{n-1} + n, \:\text{for}\: n \geq 1, \:\text{with}\: a_{0} = 1$
Use question $48$ to solve the recurrence relation $(n + 1)a_{n} = (n + 3)a_{n-1} + n, \:\text{for}\: n \geq 1, \:\text{with}\: a_{0} = 1$
admin
230
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
196
Kenneth Rosen Edition 7 Exercise 8.2 Question 48 (Page No. 526)
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$ ...
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} = ...
admin
414
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
197
Kenneth Rosen Edition 7 Exercise 8.2 Question 47 (Page No. 526)
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 $\ ... year of employment. Solve this recurrence relation to find her salary for her $n^{\text{th}}$ year of employment.
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...
admin
590
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
198
Kenneth Rosen Edition 7 Exercise 8.2 Question 46 (Page No. 526)
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 ... assuming that n goats are removed during the $n^{\text{th}}$ year for each $n \geq 3.$
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 r...
admin
495
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
199
Kenneth Rosen Edition 7 Exercise 8.2 Question 45 (Page No. 526)
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. ... $n$ months after one pair is left on the island.
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 rab...
admin
390
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
200
Kenneth Rosen Edition 7 Exercise 8.2 Question 44 (Page No. 526)
(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}.$
(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 el...
admin
246
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
201
Kenneth Rosen Edition 7 Exercise 8.2 Question 43 (Page No. 526)
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}.]$
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} =...
admin
190
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
202
Kenneth Rosen Edition 7 Exercise 8.2 Question 42 (Page No. 526)
Show that if $a_{n} = a_{n-1} + a_{n-2}, a_{0} = s\:\text{and}\: a_{1} = t,$ where $s$ and $t$ are constants, then $a_{n} = sf_{n-1} + tf_{n}$ for all positive integers $n.$
Show that if $a_{n} = a_{n-1} + a_{n-2}, a_{0} = s\:\text{and}\: a_{1} = t,$ where $s$ and $t$ are constants, then $a_{n} = sf_{n-1} + tf_{n}$ for all positive integers $...
admin
170
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
203
Kenneth Rosen Edition 7 Exercise 8.2 Question 41 (Page No. 526)
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}$ is greater ... for which $n\: f_{n}$ is less than $\dfrac{1}{\sqrt{5}}\left(\dfrac{1 + \sqrt{5}}{2}\right)^{n}.$
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 + \s...
admin
214
views
admin
asked
May 6, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
204
Kenneth Rosen Edition 7 Exercise 8.2 Question 40 (Page No. 526)
Solve the simultaneous recurrence relations $a_{n} = 3a_{n-1} + 2b_{n-1}$ $b_{n} = a_{n-1} + 2b_{n-1}$ with $a_{0} = 1 \: \text{and}\: b_{0} = 2.$
Solve the simultaneous recurrence relations$a_{n} = 3a_{n-1} + 2b_{n-1}$$b_{n} = a_{n-1} + 2b_{n-1}$with $a_{0} = 1 \: \text{and}\: b_{0} = 2.$
admin
1.3k
views
admin
asked
May 5, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
205
Kenneth Rosen Edition 7 Exercise 8.2 Question 39 (Page No. 526)
a) Find the characteristic roots of the linear homogeneous recurrence relation $a_{n} = a_{n-4}.$ [Note: These include complex numbers.] Find the solution of the recurrence relation in part $(A)$ with $a_{0} = 1, a_{1} = 0, a_{2} = -1,\: \text{and}\: a_{3} = 1.$
a) Find the characteristic roots of the linear homogeneous recurrence relation $a_{n} = a_{n-4}.$ [Note: These include complex numbers.]Find the solution of the recurrenc...
admin
215
views
admin
asked
May 5, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
206
Kenneth Rosen Edition 7 Exercise 8.2 Question 38 (Page No. 526)
Find the characteristic roots of the linear homogeneous recurrence relation $a_{n} = 2a_{n-1} - 2a_{n-2}.$ [Note: These are complex numbers.] Find the solution of the recurrence relation in part $(A)$ with $a_{0} = 1\:\text{and}\: a_{1} = 2.$
Find the characteristic roots of the linear homogeneous recurrence relation $a_{n} = 2a_{n-1} - 2a_{n-2}.$ [Note: These are complex numbers.]Find the solution of the recu...
admin
920
views
admin
asked
May 5, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
207
Kenneth Rosen Edition 7 Exercise 8.2 Question 37 (Page No. 526)
Let an be the sum of the first $n$ triangular numbers, that is, $a_{n} = \displaystyle{}\sum_{k = 1}^{n} t_{k},\:\text{where}\: t_{k} = k(k + 1)/2.$ Show that $\{an\}$ satisfies the linear nonhomogeneous ... and the initial condition $a_{1} = 1.$ Use Theorem $6$ to determine a formula for $a_{n}$ by solving this recurrence relation.
Let an be the sum of the first $n$ triangular numbers, that is,$a_{n} = \displaystyle{}\sum_{k = 1}^{n} t_{k},\:\text{where}\: t_{k} = k(k + 1)/2.$ Show that $\{an\}$ sat...
admin
260
views
admin
asked
May 5, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
208
Kenneth Rosen Edition 7 Exercise 8.2 Question 36 (Page No. 526)
Let an be the sum of the first $n$ perfect squares, that is, $a_{n} = \displaystyle{}\sum_{k = 1}^{n} k^{2}.$ Show that the sequence $\{a_{n}\}$ ... initial condition $a_{1} = 1.$ Use Theorem $6$ to determine a formula for $a_{n}$ by solving this recurrence relation.
Let an be the sum of the first $n$ perfect squares, that is, $a_{n} = \displaystyle{}\sum_{k = 1}^{n} k^{2}.$ Show that the sequence $\{a_{n}\}$ satisfies the linear nonh...
admin
190
views
admin
asked
May 5, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
1
answer
209
Kenneth Rosen Edition 7 Exercise 8.2 Question 35 (Page No. 526)
Find the solution of the recurrence relation $a_{n} = 4a_{n-1} - 3a_{n-2} + 2^{n} + n + 3\:\text{with}\: a_{0} = 1\:\text{and}\: a_{1} = 4.$
Find the solution of the recurrence relation $a_{n} = 4a_{n-1} - 3a_{n-2} + 2^{n} + n + 3\:\text{with}\: a_{0} = 1\:\text{and}\: a_{1} = 4.$
admin
385
views
admin
asked
May 5, 2020
Combinatory
kenneth-rosen
discrete-mathematics
counting
recurrence-relation
descriptive
+
–
0
votes
0
answers
210
Kenneth Rosen Edition 7 Exercise 8.2 Question 34 (Page No. 526)
Find all solutions of the recurrence relation $a_{n} =7a_{n-1} - 16a_{n-2} + 12a_{n-3} + n4^{n}\:\text{with}\: a_{0} = -2,a_{1} = 0,\:\text{and}\: a_{2} = 5.$
Find all solutions of the recurrence relation $a_{n} =7a_{n-1} - 16a_{n-2} + 12a_{n-3} + n4^{n}\:\text{with}\: a_{0} = -2,a_{1} = 0,\:\text{and}\: a_{2} = 5.$
admin
230
views
admin
asked
May 5, 2020
Combinatory
kenneth-rosen
discrete-mathematics
descriptive
counting
recurrence-relation
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
12
...
91
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register