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) = ...
2
votes
3answers
82 views
Solving recurrence equation using exponential generating functions
The recurrence is
$ a_n = (n-1) a_{n-1} + (n-2)a_{n-2} $
I tried using exponential generating functions and have problems with it (the second term mostly)
Further can this be solved without ...
2
votes
5answers
102 views
Deriving Closed Form for a Recursion via Generating Functions
Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$.
Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain
$$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...
2
votes
1answer
25 views
Finding the coefficient in the closed form of the generating function
I try to solve the recursion $a_n=5a_{n-1}+5^n$ with $a_0=1$ with generating function, but I could not find the coefficient of $x^n$ in the closed form
\begin{eqnarray*}
...
2
votes
2answers
38 views
Using Generating Functions (again) to Solve Recurrences
Consider the recursion $a_n = 2a_{n-1} + (-1)^n$ where $a_0 = 2$
Then $A(x) = \sum a_n x^n$ = $2 + \sum a_n x^n$ shifting the index of summation. The only next move I can think of is to now ...
2
votes
3answers
87 views
Solving functional equation for generating function
Find the functional equation for the generating function whose coefficients satisfy $$
a_n = \sum_{i=1}^{n-1}2^ia_{n-i}, \text{ for } n\ge 2, a_0 = a_1 = 1
$$
This is what I've tried so far:
$$
...
2
votes
1answer
38 views
Finding functional equation for generating function
I'm given
$$
a_n = \sum_{i=2}^{n-2} a_ia_{n-i} \quad (n\geq 3), a_0 = a_1=a_2 = 1
$$
and I need to find the functional equation for the generating function satisfying the above equality. I obtained ...
2
votes
2answers
65 views
Functional equations and generating functions
The problem asks to find the functional equations for the generating functions whose coefficients satisfy
$$
a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}\,\, (n\geq1), a_0 = 1
$$
There's an example that's ...
-2
votes
1answer
174 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 = ...
1
vote
2answers
69 views
Solving Another Recursion Using Generating Functions
I am trying to find a closed form for
$$
Y(n) = Y(n-1) -2Y(n-2) + 4^{n-2} \text{ with initial conditions } Y(0) = 2,Y(1) = 1
$$
using generating functions. However, I am still not entirely ...
2
votes
2answers
75 views
Using Generating Functions to Solve Recursions
I have the recursion $A(n) = A(n-1) + n^2 - n$ with initial conditions $A(0) = 1$. I attempted to solve it using generating functions and I'm not quite sure I have it right, so I thought I might ask ...
6
votes
2answers
67 views
Generating Functions: Solving a Second-Order Recurrence
I'm self-studying generating functions (using GeneratingFunctionology as a text). I came across this programming problem, which I immediately recognized as a modification of the Fibonacci sequence. ...
3
votes
5answers
160 views
How to create a generating function / closed form from this recurrence?
Let $f_n$ = $f_{n-1} + n + 6$ where $f_0 = 0$.
I know $f_n = \frac{n^2+13n}{2}$ but I want to pretend I don't know this. How do I correctly turn this into a generating function / derive the closed ...
4
votes
2answers
115 views
A Recurrence Relation Involving a Square Root
Consider the recurrence relation:
$a_{n+1} = \sqrt{a_n^2 -k},$
where $k>0$, $n\in\{0,1,n:a_n^2\geq k\}$, and $a_0>0$ is known.
Is it possible to obtain an expression for $a_n$ in terms of ...
2
votes
3answers
51 views
generating functions, can't seem to get the correct answers.
So, I've been having some issues with generating functions and counting problems. An example problem is: $$ a_n = a_{n-1} + 9a_{n-2} - 9a_{n-3} \;\;\; (n \geq 3)$$
Where $a_0 = 0, a_1 = 1, a_2 = 2$
...
1
vote
2answers
31 views
Solving a recurrence based on the solution to another.
I have a solution to a recurrence $g(n)=f(n) + g(n-1)$, and I'd like to solve the recurrence $h(n) = \alpha[f(n) + h(n-1)]$. I guessed the solution was $h(n) = \alpha^ng(n)$, but it turns out this ...
0
votes
2answers
78 views
Solving for a Generating Function in a Special Case
I'm trying to teach myself about generating functions by following this text. I've hit a stumbling block in one of the exercises left for the reader (Sec. 1.4), which I'd quite like to resolve before ...
0
votes
3answers
61 views
Still stuck on recurrence
I am still stuck on this problem and it is very frustrating. I need to solve this using exponential generating series and again with telescoping. Problem is I am not even sure what telescoping is and ...
0
votes
2answers
114 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?
2
votes
3answers
116 views
How to solve second degree recurrence relation?
For first degree recurence relation it is as simple as $f(n)=a^n\cdot f(0)+b\dfrac{a^n-1}{a-1}$.
But how do you solve second degree?
For example
$$f(n)=\begin{cases}
1,&\text{for }n=1\\
...
4
votes
4answers
204 views
The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$
A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number ...
0
votes
0answers
94 views
To obtain the closed-form expression of CDF and PDF from the recurrence relation
Now I have a question, in which I need to find the probability mass function and the cumulative distribution function. But now I only have the recurrence relation. Here is the details:
Assume ...
3
votes
1answer
235 views
Explicit Formula Given a Recursion
Suppose we have a function $f$ such that for positive integers $n \ge1$ and $f(0)=0$ and $f(1)=1$ we have:
i) $f(2n + 1) = 2f(n) + 2$
ii) $f(2n) = f(n) + f(n − 1) + 2$
What is the generating ...
0
votes
2answers
62 views
convert generating function to recurrence
How do we convert generating function to a recurrence:
Lets say we have this function
\[ x\mapsto
x\cdot \frac{8+2x-2x^2}{1-6x-3x^2+2x^3} \]
how do we get it back to a recurrence?
3
votes
2answers
129 views
How to solve the differential equation $u_k(z)=-2\cfrac{\partial}{\partial z }(\cfrac{u_{k+1}(z)}{z})$?
$$e^{z\sqrt{1-t}}=\sum \limits_{k=0}^\infty \frac{u_k(z)t^k}{k!}$$
$$\frac{\partial}{\partial t }(e^{z\sqrt{1-t}})=\frac{\partial}{\partial t }(\sum \limits_{k=0}^\infty \frac{u_k(z)t^k}{k!})$$
...
3
votes
4answers
138 views
Expansion of $x^4\over1+x^2$ into a power series
I calculated the generating function $A(x)$ of the recurrence $a_n = a_{n-2} - 2a_{n-3}$, $(n \ge 0, a_0 = a_1 = 0, a_2 = 2)$ and I have no clue on how to expand it into a power series in order to ...
0
votes
0answers
188 views
What are the mathematical and “real world” applications of “quadratic maps”, a type of dynamical system?
If we suppose that we can get a generating function for any "quadratic map (as in dynamical systems)", what are the mathematical applications? Also, what are the "real world" applications of this? ...
0
votes
1answer
36 views
Recurrence relation, error in generating function - where did I go wrong?
This is the homework. If you are interested in precise formulation, it is as follows: write a recurrence relation and a generating function that would generate a sequence of trites (elements of a set ...
2
votes
0answers
187 views
Asymptotics for the expected length of the longest streak of heads.
As Introduction to Algorithms (CLRS) describes, the problem is
Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see?
The book claims ...
8
votes
1answer
389 views
How to solve this recurrence
Solve the recurrence
\[
f_{j,k}^{(l)} =
\begin{cases}
\left[j>k\right] j^{k-1}(j-k), &\qquad j=l \\
\\
\left[j>k+1\right] \sum_t \binom k t f_{j-1,k-t}^{(l)}, &\qquad j>l
\end{cases}
...
13
votes
3answers
396 views
Solving a difficult recursion via generating functions
I have been trying to solve the recurrence:
\begin{align*}
a_{n+1}=\frac{2(n+1)a_n+5((n+1)!)}{3},
\end{align*}
where $a_0=5$, via generating functions with little success. My progress until now is ...
5
votes
1answer
189 views
A nicer recurrence for the Eulerian polynomials.
I was perusing the subject of Eulerian polynomials. I'm assuming the definition that the Eulerian polynomial is defined by $C_n(t)=\sum_{\pi\in S_n}t^{1+d(\pi)}$, where $d(\pi)$ is the number of ...
5
votes
1answer
201 views
Recurrence for perfect matchings revisited.
I like to study combinatorics a bit as a hobby, and recently a question I found interesting was posed asking to derive a recurrence for the generating function $G_n(x)$, the ordinary generating ...
1
vote
0answers
103 views
Find $G(n)$ with $n \geq 1$
Let $G(1) = 0, \ G(2) = 1$, $G(2n+1) = 2 + G(n) + G(n+1)$ and $G(2n) = 1 + G(n), \ \ n \geq 1$
Find $G(n) $
P.S: This is little problem in my problem. I tried to solve by using generating function, ...
1
vote
2answers
321 views
Recurrence relations and Generating functions - how to find the initial conditions?
Best to ask by example. Given the recurrence relation $a_{n}=a_{n-1}+a_{n-2}$, and some given initial conditions, we can find a similar relation for the generating function for the sequence, ...
2
votes
3answers
160 views
Solving $A(x) = 2A(x/2) + x^2$ Using Generating Functions
Suppose I have the recurrence:
$$A(x) = 2A(x/2) + x^2$$ with $A(1) = 1$.
Is it possible to derive a function using Generating Functions? I know in Generatingfunctionology they shows show to solve ...
0
votes
3answers
69 views
What is the $n$-th sequence element for the generating function $\frac{1}{(1-ax)^2}$?
for e.g. for $\frac{1}{(1-ax)} = a^n$
or for $\frac{1}{(1-x)^2} = n+1$
generating function = $\frac{1}{(1-ax)^2}$
2
votes
2answers
145 views
Recurrence $A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$
What is the general approach to solving this recurrent equation given that $p(x)$ and $q(x)$ are not constant and do not depend on $n$ and $p(x)+q(x) \neq 1$. Please just give me some hints, don't ...
2
votes
2answers
88 views
Problem with generating functions and binary recurrences
I am considering the following recurrence:
$a_0 = 1$;
$a_1 = 2$
$a_{n} = 2 (a_{n - 1} + a_{n - 2})$
Then I proceeded with the generating function:
$F(x) = \displaystyle\sum_{n = 0}^\infty a_n x^n ...
3
votes
1answer
195 views
Expanding the generating function of the Fibonacci numbers to find a cute formula
$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
3
votes
1answer
367 views
On the generating function of the Fibonacci numbers
Let's define the Fibonacci numbers as $F_0=1$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$. Using this recurrence I was able to calculate the generating function of the Fibonacci numbers to be ...
6
votes
1answer
165 views
What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?
The question sounds simple: find the roots of the characteristic equation, take the one with the largest absolute value, and find its coefficient. Repeated roots do not substantially complicate ...
5
votes
3answers
284 views
How to solve this recurrence using generating functions?
Exercise:
For $n \geq 0$ let $a_n = \sum \limits_{i=0}^n (i^2- 2i + 1)$
a) Show that $$a_{n+4} -4a_{n+3} + 6a_{n+2} - 4a_{n+1} + a_n = 0, n \geq 0$$
b) Identify the genereating series ...
6
votes
1answer
250 views
Generating function of words in a binary alphabet counting blocks and appearances
Given the binary alphabet {a,b}, I'm trying to find the generating function that distinguishes, for all words of fixed length $n$, the count of blocks of a's and the number of a's. Let $x^p$ count the ...
8
votes
2answers
525 views
Solving recurrence relations that involve all previous terms
I'm not sure if this a proper recurance relation per se but I'd be interested in the methodology in solving a recurrence relation of the following form:
$Z_0 = 1$
$Z_1 = x_1$
$Z_2 = x_1Z_1 + x_2 = ...
