Questions regarding functions defined recursively, such as the Fibonacci sequence.

learn more… | top users | synonyms

2
votes
2answers
104 views

Growth of a sequence satisfying a linear recurrence

A paper I am reading says that a sequence satisfying a linear recurrence grows either polynomially or exponentially. Is this easy to see?
2
votes
2answers
143 views

Computation of characteristic polynomial fails for me

For a matrix $A\in\mathbb{K}^{n\times n}$ where $\mathbb{K}\in\{\mathbb{R},\mathbb{C}\}$ the characteristic polynomial is defined as $$\chi_A(\lambda) := \text{det}(A-\lambda I_n) = \sum_{k=0}^n c_k ...
2
votes
2answers
375 views

Representing affine transform of Legendre polynomials

I have a function defined as a set of weighted Legendre polynomials: $f(x)=\alpha_0 P_0(x) + \alpha_1 P_1(x) + \alpha_2 P_2(x) +\ldots$. I have another function similarly defined with Legendre basis ...
2
votes
1answer
333 views

Proof of closed form Hofstadter G-Sequence

I'm working through a discrete maths text book and was stumped as to how to prove the closed form solution of the Hofstadter G-Sequence $a(0) = 0$ and $a(n) = n - a(a(n-1)), n \geq 1$ The closed ...
2
votes
1answer
37 views

Unsolveable equation?

If we have the inhomogenous recurrence relation $$f(n+2) - 6f(n+1)+9f(n) = 6*3^{n} + 2^{n} = 2 * 3^{n+1} + 2^n, f(0) = 0, f(1) = 1, n \ge 1$$ Step 1: Find the homogenous solution $f(n) = C_13^n + ...
2
votes
1answer
65 views

Recurrence vs Recursive

Say team 1 is studying the recursive characteristics of a function. Team 2 is studying the recurrent characteristics of the same function. Are the 2 teams studying the same thing? I have found for ...
2
votes
1answer
28 views

Intersection of two recurrences.

I have two sequences obtained by recurrences: $$f(0) = 1, f(1) = 9, f(n+2) = 10f(n+1) - f(n)$$ $$g(0) = 1, g(1) = 7, g(n+2) = 6g(n+1) - g(n)$$ How can I prove that apart from $f(0) = g(0) = 1$, these ...
2
votes
2answers
28 views

MNTILE SPOJ Tiling patterns

We have tiles of size 2 * 1. We need to arrange the tiles to get the floor size of m * n. For ...
2
votes
1answer
31 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
2
votes
1answer
23 views

Clarification regarding the Josephus problem in Concrete Mathematics (Knuth, et al)

In page 9 of Concrete Mathematics, regarding the Josephus Problem, they state that "each person's number has been doubled then decreased by 1". $J(2n) = 2J(n) - 1$, for $n \ge 1$ I don't quite ...
2
votes
1answer
41 views

Linear recurrence relation in Cantor-like sets

I have a linear recurrence relation $$a_i = \alpha_0 a_{i-1} + \beta(i)$$ Where $\beta(i) = \beta_0b_i$ with $b_i \in \{0,1\}^\mathbb N$ I know that $0 < \alpha_0 < \frac{1}{2}$, $\beta_0 = 1 ...
2
votes
1answer
56 views

Filling of a tank - recurrence relation

Suppose a tank has a maximum limit of 100 units. Each day 2,1 and 0 units are added to the water level with probability p,r and q. Any excess water would overflow and if it reaches the minimum level ...
2
votes
1answer
66 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}) ...
2
votes
1answer
131 views

Integral involving the Spherical Bessel Function of the First Kind

How can I prove the equation below using Spherical Bessel Function Recurrence Relation? (where $ j_{n}(x) $ means Spherical Bessel function of first kind) Definition using BesselJ function: $$ ...
2
votes
2answers
106 views

Non homogeneous Recurrence relation problem

So here i have this non homogeneous recurrence relation i need to solve: $$a_{n}=12a_{n-2}+16a_{n-3}+9\cdot 4^{n}+81n,$$ where $a_{0}=0$, $a_{1}=1$ $a_{2}=98$. I'm confused at the homogeneous ...
2
votes
3answers
71 views

Proof by induction of a recursive sequence

I am studying CIE A levels Further Maths and I am stuck at a question from June 2002: Q The sequence of positive numbers $u_1,u_2,u_3,...$ is such that $u_1<4$ and ...
2
votes
1answer
57 views

Find the generating function for a series , given a recurrence relation

I am solving a problem on an Online Judge. The problems solution boils down to find the solutions to the following recurrence relation: ...
2
votes
1answer
86 views

Recurrence relation converting to explicit formula

Let $a_n = -2a_{n-1 }+ 15a_{n-2 }$ with initial conditions $a_1 = 10 $ and $a_2 = 70$. a)Write the first 5 terms of the recurrence relation. b)Solve this recurrence relation. c)Using the explicit ...
2
votes
5answers
93 views

How to find first five terms of sequence?

I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$ I ...
2
votes
1answer
35 views

Recurrence relation and big-O-notation

Consider the following recurrence relation: $$T(n)=c\cdot + 2\cdot T(n/2)$$ This is the recurrence relation for the Merge-Sort algorithm. How can one deduce from this equation the time complexity of ...
2
votes
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 ...
2
votes
1answer
47 views

Solving the recurrence relation $T(n) = (n+1)/n*T(n-1) + c(2n-1)/n, T(1) = 0$

I tried a lot of different methods. Not able to make out the series. Could anyone help me i this regard? $ T(n) = \frac{(n+1)}{n}T(n-1) + c\frac{(2n-1)}{n} , T(1) = 0 $
2
votes
2answers
69 views

Got stuck in proving monotonic increasing of a recurrence sequence

I'm stuck with the prove of the following recurrence sequence which was part of and old exam. $a_1:=\frac{1}{2}, a_{n+1}:=a_n(2-a_n)$ for $n \in \mathbb{N}$ I have to show that $0 <a_n < 1$ ...
2
votes
2answers
55 views

Question with recurrence - Check my answer and suggest better ideas

Every morning when he gets up, Oria leaves the house for a walk. he walks exactly $n$ steps. He can walk only forward, right, or left, and he will never turn left immediately after he turned right, ...
2
votes
5answers
109 views

Finding a recurrence relation in combinatorics

First, my English is not that good so please don't laugh. I need to find a recurrence relation for : The number of words with the length of n that could be composed from the letters A,B,C,D, so the ...
2
votes
1answer
51 views

Recursive Definition for Logarithm

Is it possible to express $\log(n)$ in terms of itself, using only elementary functions, e.g., similar to (the incorrect made-up equation): \begin{equation*} \log(n) = e^n * \log(n - 1) + \sin(n) * ...
2
votes
1answer
105 views

The annihilator of $n(2^n)\sin({n\pi \over 2})$

I have to solve this problem: $y(n+2)-y(n)=n(2^n)\sin({n\pi \over 2})$ And I know the annihilator of $n(2^n) = (E-2)^2$, but I don't know how I should find the other part of the annihilator. ...
2
votes
1answer
113 views

Closed form solution to a recurrence relation (from a probability problem)

Is there a closed form solution to the following recurrence relation? $$P(i,j) = \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$ where $P(i,j)=0$ for $j<5$. The ...
2
votes
1answer
74 views

Recurrence relations - simple questions, please verify my answers.

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving ...
2
votes
1answer
94 views

How find this function $f(2^m)=?$

show that:there exists unique function $f:N^{+}\to N^{+}$,such $$f(1)=f(2)=1$$ and $$f(n)=f(f(n-1))+f(n-f(n-1))),n=3,4,\cdots$$ and Find $f(2^m),m>2,m\in N$ My try: let $n=3$ ,then we have ...
2
votes
1answer
261 views

Recurrence relations question

A vending machine dispensing books of stamps accepts only one-dollar coins, $1 bills, and $5 bills. a) Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, ...
2
votes
1answer
54 views

How to solve this specific recurrence relation

I'm trying to solve the following recurrence relation for $\alpha_j$, for which Mathematica is not helpful. $$ \lambda\alpha_j + (j+1)\alpha_{j+1} = \sum_{\mu = ...
2
votes
1answer
361 views

Recurrence relation and ternary sequences

I had a question that I need some help on: Find and solve a recurrence relation for the number of n-digit ternary sequences with no consecutive digits being equal As I worked this out, I ...
2
votes
2answers
434 views

Nonhomogeneous Recurrence Relations

Solve the nonhomogeneous recurrence relation $$h_{n}=3h_{n-1}-2$$ $$n\geq 1$$ $$h_{0}=1$$ I have been told to approach this type of problem using two steps. First, solve the corresponding ...
2
votes
1answer
34 views

Simple recurrence relation - 1D

I know this is a very simple recurrence relation, but how would you go on solving it? $$x(n+1)=\frac{x(n)}{1+x(n)}$$
2
votes
1answer
104 views

Basis for recurrence relation solutions

So, I have a question: Imagine a recurrence relation $U(n+2) = 2U(n+1) + U(n)$. How do I determine the dimension (and the vectors that constitute the basis) of a vector space which contains all ...
2
votes
1answer
79 views

Looking for bounds of a recursively defined sequence

I'm looking for the tightest upper and lower bounds on the sequence defined recursively by $a_{0}=1$ and $a_{n}={\displaystyle \sum_{k=0}^{n-1}\frac{4}{n^{2}}a_{k}+c\cdot n}$ for $c>0$. It is ...
2
votes
1answer
60 views

How to prove and derive coefficients that an exponential whose base decreases exponentially is a parabola

Suppose I have a function defined by this recurrence-relation: $$R(0) = r$$ $$R(n) = R(n-1) * (1+G)d^{n-1}$$ Here r is a base value, G is a base growth rate (G>0) and d is a decay in the growth rate ...
2
votes
3answers
572 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
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*} ...
2
votes
2answers
80 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
2answers
77 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, ...
2
votes
1answer
52 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
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
1answer
138 views

Pascal Triangle Related Problem: Fibonacci Sequence on sides

I have this triangle: $$\begin{array}{} &&&&&&&1\\ &&&&&&1&&1\\ &&&&&2&&2&&2\\ ...
2
votes
1answer
1k views

Showing that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$

How can we prove that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$? What is the resulting equation I get after the substitution? $$ T(n) = 2c \cdot \frac n2 \cdot \log \frac n2 + 17 + n $$ ...
2
votes
1answer
76 views

Constant term of recursively defined polynomials related to the Lambert W function

The Lambert $W$ function has the property that $$ W'(x) = \frac{W(x)}{x[1+W(x)]}, $$ and using this one can show that its Taylor expansion about $x=a$ has the form $$ W(x) = W(a) + ...
2
votes
1answer
531 views

Concrete Mathematics - The Josephus Problem

I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem. Recurrent relation: $J(1) = 1$ $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + ...
2
votes
4answers
425 views

Solving Recurrence T(n) = T(n − 3) + 1/2;

I have to solve the following recurrence. $$\begin{gather} T(n) = T(n − 3) + 1/2\\ T(0) = T(1) = T(2) = 1. \end{gather}$$ I tried solving it using the forward iteration. $$\begin{align} T(3) ...
2
votes
2answers
115 views

When is a linear recurrence relation solvable?

I was reading this definition of a linear recurrence, and was wondering what characteristics are required of a linear recurrence for it to be solvable? Meaning, can I find a closed form? The subject ...