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

learn more… | top users | synonyms (2)

7
votes
1answer
245 views

Compute limit of the sequence $x_n$ given by $x_{n+2}=-\frac{1}{2}(x_{n+1}-x_n^2)^2+x_n^4$

Let $(x_n)$ be a real sequence such that $x_0=a\in\mathbb{R},x_1=b\in\mathbb{R},x_{n+2}=-\dfrac{1}{2}\left(x_{n+1}-x_{n}^2\right)^2+x_{n}^4\;\forall n\in\mathbb{N} $ and $|x_n|\leq ...
4
votes
0answers
641 views
+50

How to solve non-linear recurrence relation in general?

For linear recurrence, we can use generating function. So is there a general technique to solve non-linear recurrence or it depends on a specific sequence? For example, $$a_{n+1} = \dfrac{a_n(a_n - ...
3
votes
0answers
42 views

Relation between 2 recurrence equations.

I am stuck with the following recurrence relations (actually asked in a programming question).Given the following relationships, is it possible to find the index of the occurrence of any given number ...
0
votes
1answer
23 views

Polynomials: functions of functions integer roots

I'm attempting to prove: Define functions $f_m$ by the recursion relation such that $f_1(x) = 2x^2-1$ and $f_k(x) = f_1(f_{k-1}(x))$ . Then for all $ m > 0$, there exists no $x \in \mathbb Z$ ...
0
votes
1answer
13 views

Solving second order difference equations with non-constant coefficients

For the difference equation $$ 2ny_{n+2}+(n^2+1)y_{n+1}-(n+1)^2y_n=0 $$ find one particular solution by guesswork and use reduction of order to deduce the general solution. So I'm happy with ...
0
votes
1answer
1k views

Implementing discrete Poisson equation wtih Neumann boundary condition

I understand how to implement a discrete 2D poisson solution with Dirchlet boundary conditions. Using http://en.wikipedia.org/wiki/Discrete_Poisson_equation#On_a_two-dimensional_rectangular_grid , you ...
0
votes
1answer
30 views

How to find a recursive formula for some sequence

I know how to find a non-recursive formula for a recursively defined sequence. However, now I have this puzzle which gives me a sequence (but not the recursive definition) and challenges me to find ...
0
votes
1answer
26 views

Creating equation for a given recurrence relation

I'm studying discrete math in the university, and we are given questions and answers for some problems, and I dont understand most of them. So I need help understanding one of them... Appreciate the ...
1
vote
1answer
10 views

Looking for a recurrence relation ot combinatorial way to calculate initial number

A flock of birds migrating south flies above seven lakes. Half of the birds in the flock, plus half a bird(I'm guessing the initial flock contained an odd number of birds, say 5, so in the first lake ...
3
votes
2answers
36 views

How to solve linear, second order ODE with Frobenius method with a difficult recurrence relation?

The ODE in question is: $$4xy''+2y'+y=0$$ Shifting the power series of each term so that they are all raised to the power $(n+r)$ will yield this recurrence relation: $$a_{n+1}={a_n\over ...
0
votes
2answers
35 views

Solve the recurrence relation (using iteration?)

$a_n = a_{n-1} + 1 + 2^{n-1}\\ a_0 = 0$ Not sure how to iterate with the exponent term. Here's what I got: $= (a_{n-2} + 1 + 2^{n-1}) + 1 + 2^{n-1} = a_{n-2} + 2 + 2(2^{n-1})\\ = (a_{n-3} + 1 + ...
2
votes
1answer
73 views

Solve the recurrence relation: $2a_n = 7a_{n-1} - 3a_{n-2}; a_0 = a_1 = 1$

$2a_n = 7a_{n-1} - 3a_{n-2}\\ a_0 = a_1 = 1$ My attempt: $2t^2 - 7t + 3 = 0\\ t = -\frac{1}{2}, -3\\ \\ U_n = b(-\frac{1}{2})^n + d(-3)^n\\ b+d = 1 = -\frac{1}{2}b-3d\\ b = \frac{8}{5}, d = ...
2
votes
1answer
39 views

Understanding Generating Function

I have been looking at This Problem and Answer about generating functions. The problem asked for the generating function of: $$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1$$ I understand how Ron Gordon ...
0
votes
1answer
24 views

Recurrence relation advice

$t_n=5t_{n-1}+6t_{n-2}$ Is the characteristic equation of this correct? This is what I have: $x$- 5$x$ -6=0 Is this correct?
5
votes
2answers
52 views

Proving a solution to a double recurrence is exhaustive

The equation $$ b^2 = \frac{a(a+1)}{2} + 1 $$ where $a$ and $b$ are integers, has the following smallish-integer solutions: ...
1
vote
3answers
33 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...
1
vote
2answers
49 views

Solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$?

What is the simplest way to solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$, with the initial values $a_0=2,a_1=1$? Is it possible to do this with generating functions?
0
votes
1answer
36 views

Solve the Recurrence

Solve the recurrence $a_k = 2a_{k-1} + 3a_{k-2}$, if $a_0 = 0$ and $a_1 = 8$. I understand how to get the generating function: $$G(x) = \sum_{k \geq0}a_kx^k = a_0 + a_1x + \sum_{k\geq 0}a_kx^k = 8x ...
0
votes
2answers
90 views

Solve the recurrence relation $x_{n+2} -3x_{n+1} + 2 x_n = n$

Solve $$x_{n+2} -3x_{n+1} + 2 x_n = n$$ when $x_0 = 1$ and $x_1 = 0$. I started with the homogen solution: $$r^2 -3r +2 = 0$$ So $$x_n^h = A1^n + B2^n$$ I know that $x_n = x_n^p + x_n^h$ But I ...
8
votes
3answers
778 views

Recursive Integration over Piecewise Polynomials: Closed form?

Is there a closed form to the following recursive integration? $$ f_0(x) = \begin{cases} 1/2 & |x|<1 \\ 0 & |x|\geq1 \end{cases} \\ f_n(x) = ...
8
votes
4answers
172 views

Help with a recurrence with even and odd terms

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\\ a(2n+1)=a(n)+a(n-1)+1 $$ I don't have much background in solving these things, so I've ...
0
votes
1answer
51 views

Multiplicative Inverse of a Power Series

For a formal power series $$F(x) = \sum p_i x^i$$ a multiplicative inverse of $F$ exists iff $p_0 \neq 0$. The inverse $\sum q_i x^i$ satisfies the recursion $$q_0 =\frac{1}{p_0}\\ q_{n} = ...
1
vote
1answer
26 views

Recurrence relation stuck on partial fraction decomposition

I am stuck in trying to solve the following recurrence relation: $$S_n = rS_{n-1} + nrB$$ where $r$ and $B$ are constants. To solve this I made the following generating function: $$f(x) = ...
1
vote
0answers
10 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
0
votes
1answer
19 views

Part of a proof recurrence relation

I'm reading this survey by Carl Offner about digit computation of the number $\pi$. In page 7 there's a step that I didn't understand: suppose $$\alpha_{n+1}=\frac{\alpha_n \beta_n}{\alpha_n + ...
0
votes
2answers
11 views

Solving a single-term recurrence relation with a variable coefficient?

$a_n = 2na_{n-1}\\ a_0 = 1$ How do I solve this? Is there a characteristic equation? I found $a_1 = 2, a_2 = 8, a_3 = 48$ but I don't know what to do with that information to solve. Please help, ...
0
votes
0answers
15 views

Solving single term recurrence relation?

$a_n = -3a_{n-1}\\ a_0 = 2$ Therefore $a_1 = -3(2) = -6\\ a_2 = -3(-6) = 18\\ a_3 = -3(18) = 54$ So... $x^n = -3^{n-1}$? If so $x^2 = -3^1$, so $x^2 + 3 = 0$, then $x = \pm (i\sqrt3)$. That doesn't ...
1
vote
2answers
38 views

two recursive sequences and the limit of their quotient

The sequences $\left \{ a_{n} \right \}$ and $\left \{ b_{n} \right \}$ are defined by the following recurrence relations: $a_{1}=b_{1}=1$ $a_{n+1}=a_{n}+2b_{n}$ $b_{n+1}=a_{n}+b_{n}$ What ...
0
votes
1answer
29 views

Simple question about recursive sequence format regarding $a(n+2) = -4a(n+1) + 5a(n)$

Suppose there's a recursive sequence $a(n+2) = -4a(n+1) + 5a(n)$ How can i convert it into the form $a(n)$ because I am most comfortable solving questions in this form. I tried to find out but I'm ...
1
vote
1answer
58 views

How to approach an equation of the form $f(x)=y$ where $f$ is recursively defined? [duplicate]

This is a homework problem so I am not looking for someone to solve it for me. I would like to know how I should approach this problem, or in what direction I should research to figure it out myself. ...
0
votes
1answer
22 views

Recurrence relation of distances between $n$-dimensional curves

I have a problem involving recurrence and euclidean distances in $n$-dimensional curves. Given the sequence of curves in $\mathbb{R}^n:$ $\{ x_{1}^2+x_{2}^2+\cdots + x_{n}^2 = 1, ...
0
votes
1answer
23 views

Finding the inverse of a recursive function?

Let's say I have this function $$f(x) = \sum_{i=0}^{x-1}f(i)$$ provided $f(0) = 0, f(1) = 1$ and $x \in \mathbb Z$. This function is evidently one-to-one on $[3, \infty) $. Is there an inverse to this ...
0
votes
4answers
48 views

How to prove the sequence given by $a_{n+1}=s+a_n^2$ is monotonic increasing?

Let $s$ be $0\:\le \:s\le \:\frac{1}{4}$ and consider this sequence: $a_1\:=\:s$ $a_{n+1}\:=\:s\:+\:a_n^2$ I want to prove that is monotonic sequence, so I thought about induction or assume in ...
2
votes
4answers
34 views

General Solution for a non-Homogeneous Recurrence

What is the general solution to the recurrence: $$x(n + 2) = x(n + 1) + x(n) + n - 1$$ where $n\geq 1$ with $x(1) = 0, x(2) = 1$? It's a question on a practice exam I'm reviewing and I'm not ...
0
votes
1answer
26 views

Stuck on a difference equation which requires an A-level method

In the non-zero sequence $x[n-1]+x[n+1]=ax[n]$ and $x[n+4]=-x[n]$ i) Find possible values of $a$. ii) For what values of $b$ is $b^n$ a solution ($x[n]=b^n$)? I need to solve this using only ...
2
votes
1answer
347 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
0
votes
0answers
33 views

2nd order difference equation with n dependent coeff

I wanted to know if there was and solution to the following equation. $\left(N-n+1\right)E_{n+2} - NE_{n+1} + \left(n+1\right)E_{n} + N = 0$ Where $E_0 = 0$ and $E_1 = 2^N - 1$. $N$ is just a ...
2
votes
1answer
24 views

Number of ternary strings without consecutive zeroes

I am looking for a number of ternary strings of length n, that dont contain consecutive zeroes. This was already asked, but I am NOT looking for reccurence relation. Instead, I found this formula, ...
2
votes
1answer
40 views

Recurrence equation - floor problem

I'm having trouble solving this recurrence equation: $$x(n) = x\left(\left\lfloor \frac n2\right\rfloor \right) + n,\quad x(1)=1$$ I`m trying to find non-recurrence equation: $$x(n) = 2n - 1$$ But ...
0
votes
1answer
42 views

$\lim_{n\rightarrow \infty} a_n$ for $ a_{n+1} =a_n\cdot \frac{6+a_n}{3+2a_n}$

let there be $a_1=3$,$a_{n+1} =a_n\cdot \frac{6+a_n}{3+2a_n}$ so $a_1=3,a_2=3,etc...$ let assume there is a limit L so $L =L\cdot \frac{6+L}{3+2L}$ L=0,3 But that is not a proof, how do I continue ...
0
votes
2answers
21 views

Solving recurrence equations

Is there a method to determine the generating function for a mutually recursive recurrence equation? As an example, consider the following set if equations $$R_n = R_{n-1}+ 3P_{n-1}; R_0 = 3$$ ...
5
votes
1answer
124 views

Solving a recurrence with diagonalization?

Considering the recurrence $F_n=F_{n-1}+3F_{n-2}-3F_{n-3}$ where $F_0=0$, $F_1=1$ and $F_2=2$. Use diagonalization to find a closed form expression for $F_n$. So I first continued the recurrence to ...
-1
votes
0answers
34 views

Difference equation involving f(x+1)

Solve this equation: $B(n+1) = B(n) + iB(n) - M.$ hint: This equation can be solved by: a. Find the general solution of $B(n+1) = (1+i)B(n)$ b. Find a particular solution of $B(n+1) = B(n) +iB(n) ...
0
votes
0answers
54 views

$T(n) = T(n/2 - \log(n)) +1$ using Substitution Method

I have the following recurrence: $$T(n) = T(n/2 - \log(n)) +1$$ How can this be solved using the substitution method? I don't fully understand the theory of this method and I'm not sure how to apply ...
0
votes
1answer
35 views

Express recurrence in closed form

I am having trouble understanding the process of expressing the following recurrence in its' closed form. First of all, I do not really understand what "closed form" means. If someone could elaborate ...
1
vote
1answer
27 views

Price of a commodity converges to a limiting price

We let $Q_k$ denote the supply of commodity, $D_k$ the demand for the commodity, and $p_k$ the price at $k$-th time. The demand depends on the current price, $D_k=a+bp_k$ and the supply depends on ...
4
votes
2answers
45 views

If $f_1(k)=\sum_{i=1}^k\frac{1}{i}$ and $f_n(k)=\sum_{i=1}^kf_{n-1}(i)$, then what is $f_n(n)$?

Let $$f_1(k)=\sum_{i=1}^k\frac{1}{i},$$ and define inductively $$f_n(k)=\sum_{i=1}^kf_{n-1}(i).$$ So, $$f_2(k)=\sum_{i_2=1}^k\sum_{i_1=1}^{i_2}\frac{1}{i_1},\quad ...
1
vote
4answers
68 views

Recurrence Relation $k_{n+2}=\frac{1-n}{n+2}k_n$

There was an interesting question posted on here earlier today but it seems to have disappeared. With due to respect to the OP, I'll post the same question here from memory. If anyone finds the ...
0
votes
1answer
13 views

Recursion Relation Problem: Counting Database Identifiers Recursively

A valid database identifier of length $n$ can be constructed in three ways: • Starting with $A$ and followed by any valid identifier of length $n − 1$. • Starting with one of the two-character ...
0
votes
1answer
38 views

How can I find the order of growth of this recurrence: $T(n) =\sqrt{n}T\bigl(\sqrt{n}\bigr) + n$

I am trying to find the order of growth ($O(n)$, $O(n\log n)$) of the recurrence $T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + n$. I started to unroll the recurrence and found that I can rewrite it ...