Tagged Questions
1
vote
2answers
46 views
Help solving recurrence relation, $a_n = 3a_{n-1} + 4a_{n-2} - 12a_{n-3}$
This is in my homework, and I am not sure how to go about this, I've read the book but I can't seem to grasp what to do. Help?
$$a_n = 3a_{n-1} + 4a_{n-2} - 12a_{n-3}$$
where $a_0 = 2$, $a_1 = -1$, ...
0
votes
1answer
36 views
find recursive solution $T(n)=2T(n/2)+n-1$
I want to solve this:
$$T(n) = 2 T\left(\frac{n}{2}\right) + n - 1 $$
I try :
\begin{align*}
n &= 2^m \\
T(2^m) &= 2T(2^{m-1}) + 2^m -1 \\
2 ^ m &= B \\
T(B) ...
5
votes
3answers
53 views
Solve the recursion, $a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$
Bring the following recursion relation to an explicit expression:
$$a_n = 3a_{n-1}-3a_{n-2}+a_{n-3}+8$$
$a_{0} = 0$, $a_1 = 1$, $a_2 = 2$
All the examples I have seen were with maximum 2 steps back ...
1
vote
1answer
19 views
Details about a Recurrence Relation problem.
I am trying to understand Recurrence Relations through the Towers of Hanoi example, and I am having trouble understanding the last step:
If $H_n$ is the number of moves it takes for n rings to be ...
2
votes
1answer
68 views
Solving a recurrence relation, $a_n = \sqrt{n(n+1)}a_{n-1} + n!(n+1)^{3/2}$
I'm trying to solve the following recurrence relation, but I have a problem with the factorial part. I would like to evaluate its particular solution.
I would like also to suggest a textbook for ...
2
votes
5answers
88 views
Solving the recurrence relation [closed]
I'm interested in learning how can we solve this linear non-homogeneous recurrence relation?
$$a_z = 2a_{n-1} - 1a{n-2} + (s^2 + 1)$$
1
vote
1answer
44 views
How many times can a student skip class in a 14 weeks semester?
In a 14 weeks semester there are 5 school days each week. Johnny chooses each day if he goes to the University or skips the day. In how many ways can Johnny choose his attendance during the semester ...
1
vote
3answers
84 views
Strings and Substrings
So here is one of the last homeworks we are doing in my Discrete math class. It seems like it should be simple but I am really stuck. Any help would be greatly appreciated.
Find the ordinary ...
0
votes
3answers
27 views
Recurrence relation of two next terms
For the recurrence relation, $a_{n+2}=3a_{n+1}-2a_n$ with $a_0=2$ and $a_1=3$, compute the first six terms of the sequence and derive a closed form formula for this sequence.
So I'm totally lost with ...
3
votes
1answer
41 views
Finding a Linear Recurrence Relation
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.
...
2
votes
2answers
46 views
Recurrence Relations for $c_1$ and $c_2$
For the following recurrence relation: $a_n = 3a_{n-1}+4a_{n-2}$, where $a_0=3$ and $a_1=2$ I solved it using quadratic equation by $x^2+3x-4$. So I got to $a_n = 4^nc_1 + c_2(-1)^n$. Now to find ...
2
votes
3answers
50 views
How do I find the closed form of a recurrence relation?
I'm stuck on how to find closed forms of recurrence relations. My current problem is:
An employee joins a company in 1999 with a starting salary of $50,000. Every year this employee receives a raise ...
0
votes
1answer
23 views
Recurrence Relations: general process for solving first order
So I had asked a question prior to this one about recurrence relations, but apparently it was a bad one to ask. So I'm trying again to understand how to solve these babies... Here it is:
$$
...
1
vote
3answers
51 views
Linear Recurrence Relations
I'm having trouble understanding the process of solving simple linear recurrence relation problems. The problem in the book is this:
$$
0=a_{n+1}-1.5a_n,\ n \ge 0
$$
What is the general process, and ...
5
votes
2answers
68 views
Combinatorial explanation to following recurrence relation $a_n = 2 a_{n-1} + a_{n-2}$
Question was the following:
$a_n$ is the number of ternary strings (strings of 0,1,2) which contain no consecutive zeros and no consecutive ones. Find a formula for $a_n$?
By brute force, I found a ...
0
votes
1answer
62 views
Given a random sequence give a recurrence defining it.
I heard that there's some hard way to mechanically obtain a recurrence relation for a given sequence. Do you know something about it/where can I find information about it?
0
votes
2answers
30 views
Sequence generated by polynomial expression
For each, find the polynomial expression that gives $a_n$
1) 1, 6, 17, 34, 57, 86, 121, 162, 209, 262...
2) 4, 4, 10, 28, 64, 24, 214, 340, ...
My attempt of
1) is $3x^2+2x+1$ and
2) is $2x^2+x+4$
...
-1
votes
2answers
108 views
What the recurrence relation for this problem?
For a positive integer $n$, let $a(n)$ denote the number of ways to write $n$ as an ordered sum of integers where each summand is at least $2$. For example, $6$ can be written $6, 4 + 2, 3 + 3, 2 + ...
-2
votes
1answer
65 views
What is the recurrence relation in this problem?
Suppose that you have a large supply of red, white, green, and blue poker chips. You want to make a vertical stack of $n$ chips in such a way that the stack does not contain any consecutive blue ...
0
votes
1answer
61 views
Explicit formula for $a_n$, reccurence relations
For the following, solve each of the following recurrence relations by giving explicit formula for $a_n$ and calculate $a_9$.
$a_n = 10 a_{n-1}, a_0 = 3; $
$a_n = -a_{n-1}, a_0 = 5;$
$a_n = 3 a_{n-1} ...
0
votes
2answers
33 views
Recursive polynomial relation
So we have the following: $1^4 + 2^4 + 3^4 + ... + n^4$
How do you find a polynomial formula for this recursive relation? My attempt is to set it up as following: $(n+1)(n^3+1)$ but it does not look ...
0
votes
2answers
50 views
Recurrence relation for n-cube
For a natural number n, the n-cube is a figure created by the following recipe. The 0-cube is simply a point. For n>0, we construct an n-cube by taking two disjoint copies of an (n-1)-cube and then ...
0
votes
3answers
50 views
Recursive/Fibonacci Induction [duplicate]
1) Let $F_n$ denote the $n^t$$^h$ Fibonacci number. Prove by induction:
$$
F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\sqrt{5}}
$$
Clear ...
0
votes
3answers
35 views
Recursion Induction
Let $c_0 =3$ and for n>0, let $c_n = c_{n-1} +n.$ What is the first five terms of the sequence? Prove that $$c_n = \frac{n^2+n+6}{2}$$
Need to prove this by induction. Not a homework but I'm trying to ...
0
votes
1answer
20 views
Zero coefficient of associated homogeneous recurrence relation
When solving a non homogeneous recurrence relation, is it possible for a coefficient in the associated homogeneous equation to be zero? Meaning the solution might consist solely of the particular ...
0
votes
1answer
87 views
Solving a recurrence relation using Z transform
I'm trying to solve the following recurrence using Z transforms:
For $n\in \mathbb{N}^{*}$
$T(n)=1\ for\ n< 4$
$T(n)=T(\lfloor \frac{n}{4} \rfloor)+T(\lfloor \frac{3n}{4} \rfloor)+n\ for\ n\geq ...
0
votes
3answers
66 views
A sequence is defined by: $a(1) = 1$ and $a(n + 1) = 3a(n) - 1$ for $n \ge 1$. What is $a(100)$?
A sequence is defined by: $a(1) = 1$ and $a(n + 1) = 3a(n) - 1$ for $n \ge 1$. What is $a(100)$?
Solution. The first few terms of $a(n)$ are $1,2,5,14,\ldots$. The general solution to the ...
1
vote
3answers
84 views
Solution to a linear recurrence
What is the general solution to the recurrence: $x(n + 2) = 6x(n + 1) - 9x(n)$ for $n \geq 0$;
with $x(0) = 0; x(1) = 1$?
Solution. The first few values of $x(n)$ are $0,1,6,27,...$ The auxiliary ...
2
votes
2answers
49 views
“Fat” sets of integers and Fibonacci numbers
Let us call a set of integers "fat" if each of its elements is at least as large as its cardinality. For example, the set $\{10,4,5\}$ is fat, $\{1,562,13,2\}$ is not.
Define $f(n)$ to count the ...
0
votes
4answers
78 views
Having a lot of trouble solving this recurrence with iteration and finding a closed form…
I'm learning discrete math and didn't have any trouble with any recurrences in the examples I went over through the chapters on it, but this one problem at the end of the first chapter is killing me, ...
0
votes
1answer
72 views
Recurrence relation using the master theorem $ T(n) = 4T(n/2) + n^2 \log n$
I am trying to solve the following recurrence relation using the master theorem:
$ T(n) = 4T(n/2) + n^2 \log n$
So: $a=4 ,b=2, f(n)=n^2\log n$ , then $n^{\log_2 4}=n^2 $
Now i know that $n^2 \log n ...
1
vote
1answer
54 views
Explicit formula for recurrence relation with $A_{N+1}= A_N+{(2/7)}^N$
How can I find a non-recursive formula for the sequence $A_N$ when the sequence is defined as $A_1=1$ and for $N\ge 1$, $A_{N+1}= A_N+{(2/7)}^N$?
1
vote
1answer
61 views
Find a closed form for the recurrence relation $h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}$
I have a recurrence equation as follows:
$$h_{n}=h_{n-1}+(n-1)+\sum_{k=1}^{n-1} {n-2 \choose k-1}h_{k-1}\;,$$ with $h_{0}=0,h_{1}=1,h_{2}=2$.
2
votes
2answers
178 views
find recurrence relation $T(n)=2T(n/2) +\log_2(n)$
$$\begin{align*}
&T(n) = 2T(n/2) + \log_2(n)\\
&T(1) = 0
\end{align*}$$
$n$ is a power of $2$
solve the recurrence relation
my work so far:
unrolling this, we have
$$\begin{align*}
...
1
vote
2answers
142 views
Solving the recurrence relation $p(n,m) = n \times \sum\limits_{k=n-1}^{m-1} p(n-1,k)$ where $p(1,m) = m$
I am trying to solve the following recurrence relation
$$p(n,m) = n \times \sum\limits_{k=n-1}^{m-1} p(n-1,k)$$
$$p(1,m) = m$$ $$p(0,0)=0$$
Any hints or ideas?
(Not a homework assignment)
Edit: n ...
0
votes
2answers
110 views
Recurrence relation for the number of strings of length $n$ in base $3$
How can we find a recurrence relation for the number of strings of length $n$ in base $3$ such that the number of $1$'s and $2$'s are odd?
-1
votes
3answers
258 views
Non-homogeneous Recurrence relations
I want to solve these recurrence relations with the initial
conditions given. I know how to solve linear non-homogeneous recurrence relations with constant coefficients.
$$(a)\ \ ...
0
votes
1answer
43 views
Finding recurrence and an algorithm to represent it
You find yourself in a country with integer coin denominations $c_1 < c_2 < ... < c_r$, where $c_1 = 1$. Unfortunately, the greedy
algorithm is not guaranteed to find the optimal way to ...
1
vote
0answers
113 views
1
vote
5answers
146 views
How do we deal with recurrence relation characteristic equations that are not quadratic or have imaginary roots?
Suppose we have $$H(n) = H(n-1)-H(n-2) \rightarrow x^2-x+1 \rightarrow r_1 = \frac{1+\sqrt{-3}}{2}, r_2 = \frac{1-\sqrt{-3}}{2}$$
or
$$H(n) = H(n-1)+H(n-2)+H(n-3) \rightarrow x^3-x^2-x-1=0$$
In ...
5
votes
1answer
153 views
How to solve this recurrence relation $a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}}$?
I am trying to solve the recurrence:
$$
a_{n+2} = \sqrt{a_{n+1}\cdot a_{n}}
$$
but here is a problem for me. After few steps I have this:
$$
a_n^2 = a_{n-1}\cdot a_{n-2}
$$
and I don't now what to do ...
3
votes
2answers
134 views
Given $g(x)$, how to solve function recurrence $f(x)=af(\alpha x)+bf(\beta x)+g(x)$ where $\alpha\neq\beta$
If we have a recurrence like
$$f(x)=af(\alpha x)+bf(\beta x)+g(x)$$
where $a,b,\alpha,\beta\in\mathbb{R}$ and $\alpha\neq\beta$ and $g(x)$ is known.
How can we solve this kind of recurrence?
For ...
4
votes
3answers
117 views
How do you solve this recurrence?
I have been trying to practice recurrence relations that can be solved by the master theorem and came across this.
Now the $4^{\textrm{th}}$ problem in that file is :
$$T(n) = 2^n ...
0
votes
1answer
86 views
How do you get the upper bound over this recurrence?
$$T(n) = 4T\left(\frac{n}{2}\right) + \frac{n^2}{\log n}$$
I have the solution here (see example 4 in that pdf), but the problem is that they have solved it by guessing. I couldn't make that guess. ...
4
votes
4answers
157 views
What sort of math is this, and how would I solve it?
I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, ...
1
vote
1answer
34 views
How to approximate a complex linear homogenous recurrence with constant coefficients with a simple one?
Is there some standard way to approximate a complex linear homogenous recurrence with constant coefficients with a simple one?
For example, I might want to approximate
$$
...
5
votes
4answers
1k views
What is the solution to the following recurrence relation with square root?
This looks like a question asked earlier, but it isn't
T(n)
= T (sqrt(n)) + 1 ... if n>1
=1... if n=1
My professor gave this to me in class yesterday.
This is where I'm stuck..
T(n) ...
1
vote
1answer
125 views
How to complete this proof regarding closed form of tower of hanoi problem? [duplicate]
Possible Duplicate:
can one derive the $n^{th}$ term for the series, $u_{n+1}=2u_{n}+1$,$u_{0}=0$, $n$ is a non-negative integer
I'm trying to learn induction through practise and I'm ...
1
vote
1answer
272 views
Ulam's problem - guessing a chosen number in a set
I tried to solve the following problem, which I found in the book "Discrete Mathematics and Its Applications", by Kenneth Rosen (Problem 28 of the section 7.3 of the 6th Edition):
Suppose someone ...
4
votes
1answer
882 views
Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$
While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen:
Suppose the function $f$ satisfies the recurrence ...
