Tagged Questions

1answer
14 views

Solving (for asymptotics) of certain recurrence equations.

I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. For example ...
1answer
34 views

Initial values appear from nothing

This answer says that any casual sequence of the kind $y_n = y_{n-1} + y_{n-2} + y_{n-3} + \ldots$ will stay constant-0 because $y_0$ is a sum of zeroes, so is $y_1$ and the rest of the sequence. I ...
1answer
51 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
1answer
102 views

1answer
74 views

2answers
88 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 ...
1answer
92 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 ...
1answer
50 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)$?
2answers
64 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 ...
1answer
59 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 ...
1answer
60 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 ...
1answer
29 views

2answers
218 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, ...
1answer
73 views

2answers
71 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*} ...
2answers
56 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 ...
3answers
271 views