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

learn more… | top users | synonyms (2)

0
votes
1answer
17 views

Is it possible to solve the difference equation $K_{n+1}=aK_n+bK_n^{\theta}+c$?

Is it possible to solve the difference equation $K_{n+1}=aK_n+bK_n^{\theta}+c$, where a, b, c are real numbers while $\theta\in (0,1)$? How about $\theta=\frac{1}{2}$?
2
votes
2answers
98 views

Find $a_{2012}-3a_{2010}/3 a_{2011}$ where the sequence $a_n$ is determined by roots of a quadratic equation

If $\alpha$ and $\beta$ are the roots of $x^2-9x-3=0$, $a_n=\alpha^n-\beta^n$ and $b_n=\alpha^n+\beta^n$, then find the value of $\dfrac{a_{2012}-3a_{2010}}{3 a_{2011}}$ and ...
1
vote
0answers
19 views

Interesting recurrence equation models?

So I've had an introductory subject to recurrence equations and now I have to study a model using recurrence equations as a project. The problem is that most models I find are either elemental or ...
1
vote
2answers
534 views

Using recurrences to solve $3a^2=2b^2+1$

Is it possible to solve the equation $3a^2=2b^2+1$ for positive, integral $a$ and $b$ using recurrences?I am sure it is, as Arthur Engel in his Problem Solving Strategies has stated that as a method, ...
0
votes
1answer
30 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1}, \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form ...
-2
votes
0answers
38 views

Modifying recursion matching result

Let $f_0=\frac{1}{4}$ and $f_i=\dfrac{3f_{i-1}}{4}+\dfrac{2^{-i}}{2}$ and this gives $f_n>\frac{3^{n}}{4^{n+1}}$. This problem came as I was trying to solve a complexity theory problem. ...
0
votes
0answers
21 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
0
votes
1answer
50 views

How to solve a recurrence relation such as $T(n) = 2T(\frac{n}{2}) +$ $\frac{n}{\log (n)}$?

Wikipedia says that the equation cannot be solved using Master's Method. The equation matches with Master's Theorem except for $\frac {n}{\log(n)}$. A youTube tutor (seek time 11:42) solves this ...
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 ...
5
votes
0answers
651 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
50 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
25 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
34 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
27 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
11 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
38 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
50 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
1answer
93 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 ...
9
votes
3answers
783 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
183 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
52 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
39 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
30 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
63 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 ...