4
votes
1answer
86 views

Going from closed form to recurrence relation

If I had a closed form for a sequence that I suspect to represents a recurrence relation how would I determine the recurrence relation? In particular, I have the sequence $$a_n = ...
2
votes
2answers
58 views

Finding a Closed Form for a Recurrence Relation

I know that a general technique for finding a closed formula for a recurrence relation would be to set them as coefficients of a power series (i.e. a generating function). Then use properties of ...
1
vote
2answers
37 views

Generating function satisfying a second degree equation

I got this problem in an exercise list: Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation: $$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, ...
2
votes
1answer
66 views

Quadradic recurrence relation

There is an method to solve recurrences of the form $a_{n+1} = (a_n + c)^2$? I am particularly interested when $c = 1$. I tried to use generating functions but I got stuck with. Let $G(x) = \sum_{k ...
2
votes
1answer
64 views

Generating functions over $\mathbb{Z}$

Let $(a_n)_{n \in \mathbb{Z}}$ be a sequence such that both limits $\lim_{n \to \infty} a_n$ and $\lim_{n \to -\infty} a_n$ exists. Consider recursive relation $$ 2b_n - \frac{1}{2}(b_{n-1} + b_{n+1}) ...
0
votes
1answer
32 views

generating functions for $S(n,3)$

I would like to find a closed formula for the Stirling numbers of the second kind $S(n,3)$ or the number of ways to partition a set of 3 elements into 3 sets. I know that $S(n,3)=3S(n-1,3)+S(n-1,2)$ ...
4
votes
1answer
94 views

Is there a generating function for $\sqrt{n}$?

I tried to come up with a closed form for the ordinary generating function for the sequence $\{\sqrt{n}\}_0^{\infty}$ but I could not. Is there a way to derive it using the recurrence relation ...
3
votes
4answers
149 views

Solving the non-homogeneous recurrence relation: $g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$

$g_{n} = 12g_{n-2}-16g_{n-3}+6\cdot 2^n+25n$ With initial conditions $g_{0} = 23, g_{1} = 37, g_{2} = 42 $ This is a practice question I'm working on, and I'm running into absurd amounts of ...
1
vote
2answers
56 views

Recurrence relation with generating function problem

I've got a recurrence problem that I'm close to solving, but having trouble with finishing up. Solve the following recurrence relation using generating functions: $$g_n = g_{n-1} + g_{n-2} + ...
-2
votes
2answers
97 views

Using generation functions solve the following difference equation

Using generation functions solve the following difference equation $$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$
3
votes
2answers
98 views

Deriving a (tricky, I think?) recurrence relation

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at. "Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), ...
0
votes
1answer
39 views

Hi guys, can anyone help with this recurrence relation problem?

I'm going through practice questions for my exams but this question has left me confused: The Bessel functions of integer order, Jn(x), are described by the generating function: Derive the ...
1
vote
0answers
26 views

Deriving recurrence relations, very stuck!

Going through past papers for my exams and cannot figure this one out, does anyone know how to do these? The Bessel functions of integer order, Jn(x), are described by a generating function of the ...
3
votes
1answer
66 views

Solving a recurrence for a random walk revisited

I previously asked about the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < ...
3
votes
2answers
87 views

a manipulation of Fibonacci recurrence

Let $F_n$ be the Fibonacci number, and we know $F_{n+2} = F_{n+1} + F_{n} $ with $F_0 =1,F_1 = 1$ And this can be manipulated to $F_{n+6} = 4F_{n+3} + F_n$ if we let n be a multiple of 3, we can ...
4
votes
1answer
86 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
2
votes
1answer
43 views

Techniques for solving recurrence relations using generating functions

How does one extract coefficients from generating functions that involve exponents. Things like $A(z) = 1+A(z^2)$ or $A(z)= 1+A(z^2)+A(\sqrt z)$?
2
votes
2answers
63 views

Explicit formula for recurrence

I know how to get explicit formula for simple recurrence $a_n = m_1a_{n-1} + m_2a_{n-2}\dots$ for $m_{1,2\dots}$ being constant numbers. I'm wondering how to get explicit formula for recurrence like ...
2
votes
1answer
53 views

Generating Function for Recurrence Relation in 2 Variable

I have a recurrence relation with 2 variables similar to $$ F(n,m) = n\cdot F(n-1,m) + (n-m)\cdot F(n-1,m-1) $$ I want to know the steps required to get the generating Function for such recurences. I ...
1
vote
1answer
53 views

Solving Recurrence Relation by Generating Function Method

Im trying to solve an-7a(n-1)+10a(n-2) Im at the point where ∈aX^n-7∈a(n-1)X^n+10∈a(n-2)x^n=0 (terms of n are subscript) After this step it is given as replace the infinite sum by an expression ...
0
votes
1answer
28 views

Solving thus summation

$F_1 = 1, F_2 = 2, F_i = F_{i - 1} + F_{i - 2} (i > 2)$. A new number sequence $Ai(k)$ by the formula: $A_i(k) = F_i × i^k (i ≥ 1)$.I need to calculate the following sum: $A_1(k) + A_2(k) + ...
2
votes
3answers
102 views

Solving recurrence relation with generating functions - Nearly got the answer

I'm trying to solve the following recurrence relation (Find closed formula) using generating functions: $f(n)=10f(n-1)-25f(n-2)$, $f(0)=0$, $f(1)=1$ I'm having a small difficulty at the end and can ...
3
votes
1answer
51 views

Find the number of ways that 2n people may be paired.

Question: Find the number of ways that 2n people may be paired. I have figured this problem out, and I'm fairly certain that there are $\frac{(2n)!}{2^{n} n!}$ ways. However, I cannot seem to work ...
0
votes
1answer
65 views

Generating Function of a Recurrence Relation.

Given a sequence a(n) = a(n -2) , a(0) = 2 , a(1) = -1 Find the generating function What i have done so far: The recurrence relation is going to be a(n) - a(n-2) = 0 A = the generating function A ...
0
votes
1answer
97 views

Find a recurrent relation and generating function for the sequence

Let An be the nn matrix which has 1's on the leading diagonal and on the diagonals immediatle above and below the leading diagonal. Let an = det(An). Find a recurrent relation and generating ...
1
vote
1answer
85 views

Generating Function via Recurrence Relation

I am trying to find the solution to the following recurrence for polynomials: \begin{align*} h^{[0]}(z) &= z \\ h^{[n+1]}(z) &= z h^{[n]}(z) (z+z^2+...+z^{n+1}) +z \end{align*} I calculated ...
1
vote
1answer
154 views

Finding recurrence relation given the generating function

So I'm given the generating function $F(x)={1+2x\over1-3x^2}$ I'm supposed to find the recurrence relation satisfied by fn. I managed to get it into 2 separate geometric series and derive $f_n = ...
1
vote
2answers
200 views

Counting problem using exponential generating functions

From A Walk Through Combinatorics by Bona in the section on generating functions We have n cards. We want to split them into an even number of non-empty subsets, form a line within each subset, ...
0
votes
1answer
72 views

Solving this recursive function $f(x)=f(x-k)+f(x/k)$.

How to solve or simplify the following recursive function? $f(x)$ is defined only for whole numbers as follows: $$f(x)=\begin{cases} 1 & \mbox{if } x<k; \\ f(x-k)+f(x/k) ...
1
vote
2answers
75 views

Recurrence relation, generating function

I am trying to solve this recurrence relation using generating functions $$x_{n+2}+x_{n+1}+x_n=0$$ $$x_0 = x_1=1$$ I have got this generating function $f_a(x)=\frac{2x+1}{x^2+x+1}$. Since the ...
9
votes
0answers
246 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
1
vote
0answers
42 views

Closed form of an inhomogeneous non-constant recurrence relation

I try to find a closed form for the $f_k$'s (at least for $f_1$) satisfying the following recurrence relation for any fixed $n>0$: $f_0 = 0$, $f_n = 0$, and $f_k = \frac{n}{2k}(f_{k-1} + f_{k+1} + ...
1
vote
1answer
87 views

Recurrence $a_{n+1} = xa_n$ using generating function

I read the generating functionology, where author handles $$b_k(x) = {x \over 1-kx} b_{k-1}(x) = {x ^k \over (1-x)(1-2)(1-3x) \cdots (1-kx)}$$ since $b_0(x) = 1.$ I see that if denominator $(1-kx)$ ...
2
votes
1answer
68 views

A Generalized Fibonacci sequence

I have the following recurrence $$u_{n+1}=u_{n}+a^{N-n}u_{n-1}\quad n\ge 1$$ where $$N\ge 1,\quad u_1=u_0=1,\quad 0< a\le 1$$ I want to find out $u_N$. My Try: For $a=1$ this is just the Fibonacci ...
1
vote
0answers
58 views

Solving a recurrence involving binomials.

Does anybody know how to solve the following recurrence? Maybe with generating functions? Any hint? $t(n) = 1 + \frac{1}{2^{n-1}} \sum_{i=0}^{n-1} {n \choose i} t(i)$
1
vote
2answers
88 views

Deriving the generating function of a divide and conquer type recurrence relation

I am working through Analysis of Algorithms by Sedgewick/Flajolet On problem 3.44 I am given the recurrence, and I need to come up with a generating function. I have tried the various methods in the ...
0
votes
2answers
293 views

Recurrence relations and generating functions question

Let $A_n$ be the set of different paving of a $2\times n$ using $2\times 1$ or $1 \times 2$ tiles. We'll define $a_n$=$|A_n|$. 1] Find recurrence relation: I found it -> $a_n=a_{n-1}+a_{n-2}$ with ...
1
vote
1answer
153 views

Using partial fractions to find explicit formulae for coefficients?

The set of binary string whose integer representations are multiples of 3 have the generating function $$\Phi_S(x)={1-x-x^2 \over 1-x-2x^2}$$ Let $a_n=[x^n]\Phi_s(x)$ represent the number of strings ...
0
votes
1answer
97 views

Generating The Series

This is related to an ongoing event. It involves generating the following series : http://oeis.org/A008826 The generating Function as given in the above link is : ...
3
votes
4answers
108 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
528 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
200 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
2answers
69 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
51 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
256 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
48 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
3answers
142 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
543 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
96 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
844 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 ...