Tagged Questions
3
votes
3answers
38 views
Closed form of a recurrence relation using generating functions
It's been awhile since I have done this. The sequence is $\displaystyle a_n = a_{n-1} + 5~a_{n-2}$ with $a_{0}=0$ and $a_{1}=1$.
I found the generating function to be $\displaystyle G(x) = ...
0
votes
1answer
53 views
How to express this recurrence relation as a closed form?
I need a little help with expressing this recurrence relation as a closed form. I've already expanded it out to see the pattern:
$$
f(n) = f\left(\frac{n}{3}\right) + f\left(\frac{2n}{3}\right) + n - ...
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
66 views
Finding the expression for $q_n$
Let $q_n$ be the number of $n$-letter words consisting of letters a, b, c and d, and which contain an odd number of letters $b$. Prove that
$$q_{n+1} = 2q_n + 4^n\qquad\forall n \geq 1 $$
and, ...
1
vote
2answers
32 views
Stuck on solving recurrence relation
I'm trying to find formula for the following sequence.
1, 3, 6, 10, 15...
Recursive formula is pretty straightforward
My attempt to solve it:
Homogeneous solution
Particular solution
...
2
votes
1answer
44 views
Recurrence equation question
My question (which has been edited) relates to the following recurrence relation:
$$a_{j+2}=\frac{2 a_{j}}{j}$$
The book which I am reading says that the (approximate) solution is given by:
...
-2
votes
1answer
172 views
Find a closed form for a generating function and recurrence
Find a closed form for the generating function $R(x) = \sum_{n=0}^\infty r_nx^n$, where $r_n$ is given by the recurrence $r_n = 3r_{n-1} + 5r_{n-2} + 6n$
for $n \geq 2$ and initial conditions $r_0 = ...
2
votes
3answers
80 views
Please help solve the following recurrences
Please help with solving the recurrences to get closed form formulas for $a_n$, $b_n$ and $c_n$. Be sure to clearly label the characteristic equation, the roots of the characteristic equation, 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, ...
4
votes
5answers
180 views
What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?
What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$, $F(1)=b$ and $a,b>0$ ? It seems to be simple generalization of Fibonacci sequence but I can't find closed form for ...
3
votes
0answers
80 views
How to resolve this equation for f(n) without using f(n-1)
I have an equation related to some work I'm doing on Poisson distribution where I'm calculating a sequence of 100 values between a minimum and maximum value which is set by another formula. ...
0
votes
1answer
74 views
What is the closed form for the general recurrence relation?
$T(N) = a\cdot T(N-b) + c \cdot N + d $
$T(0) = 0$
I honestly don't understand this concept at all. Any help would be great.
1
vote
1answer
52 views
Closed form or upper bound for recursively defined sequence
Is there a closed form of the following sequence:
$$u_0 = 2$$
$$u_{n+1} = s_n^2-s_n, \;s_n = \sum_{k=0}^{n} u_k$$
If not, I would like to have an upper bound. By looking at the numbers I guessed ...
1
vote
0answers
77 views
Cycle of remainders
Let $N, K, W$ be natural numbers
If I start from $R_0$, say any integer $r_0, 0 \lt r_0 \lt N$
and proceed with:
$$R_j = ( R_{j-1} + K ) \mod W,\quad j=1,2, \dots$$
(that is the remainder of the ...
1
vote
4answers
74 views
Solving a simple recurrence.
This isn't a homework question, but it is a problem in my textbook.
Given $T(n) = T(n-1) + n$, show that $T(n) = O(n^2)$
My approach:
Given $T(n) = T(n-1)$
Need to show $T(n) = cn^2$, where $c ...
1
vote
0answers
122 views
Closed form expression for a recurrence relation.
Hello, any ideas for computing closed form for a recurrence relation?
In an attempt to compute what the $i$-th post order element would be in terms of its in order position in a complete binary tree, ...
4
votes
4answers
472 views
Closed form solution of Fibonacci-like sequence
Could someone please tell me the closed form solution of the equation below.
$$F(n) = 2F(n-1) + 2F(n-2)$$
$$F(1) = 1$$
$$F(2) = 3$$
Is there any way it can be easily deduced if the closed form ...
1
vote
1answer
145 views
Simple recurrence relation in three dimensions
I have the following recurrence relation:
$$f[i,j,k] = f[i-1,j,k] + f[i,j-1,k] + f[i,j,k-1],\quad \mbox{for } i \geq j+k,$$
starting with $f[0,0,0]=1$, for $i$, $j$, and $k$ non-negative.
Is there ...
2
votes
3answers
139 views
Find a closed term for $f(n) = n + 2 f(n-1)$, $f(1)=1$
I cannot help myself, but I don't get the closed term for: $f(n) = n + 2 f(n-1)$, where f(1) = 1. I tried to find the pattern when looking at some iterations, and I think I see the pattern very ...
0
votes
1answer
587 views
Rearranging a general closed form linear recurrence sequence
I have the following general closed form linear recurrence equation:
$$x_n=r^{n-1}a+\left(\frac{r^{n-1}-1}{r-1}\right)d, \qquad (n=1,2,3,...)$$
and the next stage in the text shows the equation ...
6
votes
4answers
123 views
closed form for $d(4)=2$, $d(n+1)=d(n)+n-1$?
I am helping a friend in his last year of high school with his math class. They are studying recurrences and proof by inference. One of the exercises was simply "How many diagonals does a regular ...
15
votes
5answers
768 views
Find a closed form for this sequence: $a_{n+1} = a_n + a_n^{-1}$
Today, we had a math class, where we had to show, that $a_{100} > 14$ for
$$a_0 = 1;\qquad a_{n+1} = a_n + a_n^{-1}$$
Apart from this task, I asked my self: Is there a closed form for this ...
