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

learn more… | top users | synonyms

3
votes
1answer
71 views

Help finding the closed formula for a recurrent relation

In the last steps of finding the complete solution of a linear differential equation by a power series, I got stuck on finding the closed formula for the following recurrent relation: $$B_n = B_{n-1} ...
1
vote
0answers
73 views

Need help with these recurrence relations

I had received some challenging recurrence last week, I did most of them except this and also one of its kind. It states Given $a_0=0$ and $a_1=1$, solve these recurrence relations: ...
3
votes
1answer
106 views

General Solution of Functional Equation

What is the general solution to: $$ \frac{f(x+h)-f(x)}{h} = \frac{1}{x} \tag{1} $$ Obviously the solution to this for the limiting case of $h\to 0$ is $f(x) = \ln(x) + c$ Attempting to solve the ...
1
vote
2answers
39 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}, ...
0
votes
1answer
40 views

Limit of recurrence relation $x_k= f(x_{k-1})$ for an increasing function $f:[0,1]\to[0,1]$

Is there a standard result out there that gives the following? It looks graphically like it must be true, but I'd like to appeal to a known result if possible. Let $f:[0,1]\to[0,1]$ be a continuous, ...
2
votes
1answer
71 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 ...
3
votes
1answer
87 views

Solving a recurrence relation ${}$

I feel I'm wasting my time trying to solve this $a_0$ is given $\displaystyle a_{n+1}=\frac{n-1}{n+2}(a_n-n-2)$ Mathematica found a closed form but there's a problem when evaluating for ...
3
votes
2answers
104 views

Determinant involving recurrence

Evaluate $$\left| A \right| = \left| {\matrix{ {x + y} & {xy} & 0 & \cdots & \cdots & 0 \cr 1 & {x + y} & {xy} & \cdots & \cdots & 0 \cr 0 ...
1
vote
1answer
68 views

Divide and Conquer (recurrence relation problem)…

The problem: (a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers. (b) Give a recurrence relation for ...
0
votes
1answer
26 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
6
votes
1answer
125 views

Limit related to the recursion $a_{n+1}=(1-n^{-1/4}a_n)a_n$

Let $0<a_{1}<1$, with $$a_{n+1}=a_{n}(1-n^{-\frac{1}{4}}a_{n})$$ Does there a real numbers $A$ which make the limit $$ ...
0
votes
3answers
47 views

Recurrence relations for students of the third year of secondary school.

I am not able to solve this problem in order to find a explicit form for the recurrence relation (note: in the original text I can read "a with n" and "a with n-1", but I am not able to format here) ...
2
votes
2answers
92 views

How to solve the recurrence $T(n) = T(n-1) +\sqrt{n}$?

While solving the recurrence of the title I come to the series $$T(n) = \sqrt1 + \sqrt2 + \sqrt{3} + \cdots + \sqrt n.$$ Please somebody help me how to solve this.
0
votes
0answers
65 views

Partial Derivative of Integration

Suppose that I have some set of weight functions, $W = \{w_1(i,j), w_2(i,j),..., w_k(i,j)\}$, where each weight function is a Taylor polynomial in $\mathbb{R}^2$ with constants $c_{kn}$ where $n$ is ...
6
votes
2answers
89 views

Is the sequence $x_{n+1} = \frac{x_n + \alpha}{x_n + 1}$ convergent?

Fix $\alpha > 1$, and consider the sequence $(x_n)_n \geq 0$ defined by $x_0 > \sqrt \alpha$ and $$x_{n+1} = \frac{x_n + \alpha}{x_n + 1}, n = 0, 1, 2, \dots$$ Does this sequence converge, ...
0
votes
0answers
33 views

Did I obtain this recursion in the Fourier domain correctly?

I would like to calculate the following recursion: $$f_n(x)=\int_{B}^{A}f_{n-1}(x-\omega)f(\omega)\mbox{d}\omega\quad\quad f_1(\omega):=f(\omega)$$ This is simply the convolution of $f$ with itself ...
0
votes
1answer
29 views

Solve the recurrence relation

Assuming that $n$ is a power of $2$, solve the recurrence relation $$T(n)=2T\left(\frac{n}{2}\right)+2$$ Take $T(2)=1$ and $T(1)=0$. Also how can this be done with the master theorem, if possible?
-4
votes
1answer
46 views

A recurrence involving nested cube roots [closed]

Solve the equatation $\sqrt[3]{x\sqrt[3]{x\sqrt[3]{x\sqrt[3]...}}} = 3$ Only have variant: 4 9 16 3
0
votes
2answers
27 views

Find the values of $r_1, r_2, r_3$ in the recurrence relation $a_n = r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $

Consider the recurrence relation $a_n = > r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $ for $n \ge 3$. The roots of the characteristic polynomial are $x = -1$ of multiplicity 2, $x= 3$ of ...
0
votes
1answer
32 views

How $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and So on?

I am currently reading 'concrete mathematics' of knuth. I don't know how $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and finally $L_0+1+2...+(n-2)+(n-1)+n $ can you please tell me?
0
votes
1answer
9 views

Solve linear homogeneous recurrent relation with constant coef using generating functions

I have the following linear homogeneous recurrent relation which I have to solve using generating functions. $a_{n+2}-2a_{n+1}-3a_n = 0$ The generating function for this is: ...
0
votes
1answer
26 views

Recurrence relation task

Can someone explain me this: $T(n)=-T(n-1)+2\times T(n-2)+3 \times 2^n+n$ According to Wolfram Alpha the answer is: $$ T(n) = c_1(-2)^n + c_2 + \dfrac{1}{18}n(3n + 7) + 3 \times 2^n - ...
1
vote
1answer
36 views

Binary string block recurrence

Let $a_n$ be the total number of blocks for all $2^n$ binary strings with length $n$. Prove the following recurrence: \begin{equation*} a_n = 2a_{n-1} + \frac{2^{n}}{2} \end{equation*} For example ...
0
votes
2answers
44 views

Complexity of $T(n) = 2T(n/2) + n$

How can I prove that $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \, \log{n})$ without master theorem , if $T(1)=\mathcal{O}(1)$? How can I continue from here? $T(n) = 2T(n/2) + n,$$T(n) = 4T(n/4) + ...
1
vote
1answer
21 views

Cardinality of a set with a recurrence relation.

Let $A = \left\{ f\in \mathbb{N}\rightarrow \mathbb{C} \mid \forall n\in \mathbb{N}. f(n+3) + 3f(n+1) = f(n+2)+f(n) \right\}$ What is $\left|A\right|$? Well, I tried to treat $f$ as a recurrence ...
5
votes
2answers
371 views

Series of sequence converges?

Given the recursively defined sequence $$ a_2 = 2(C+1)a_0 $$ and $$ a_{n+2}=\frac{\left(n(n+6)+4(C+1)\right)a_n - 8(n-2)a_{n-2}}{(n+1)(n+2)}. $$ that I got from the Frobenius method applied to an ODE, ...
2
votes
2answers
92 views

Calculate f(n+1)-f(n-1) based on f(n)???

Being: $$f(n) = \left(\frac{5+3\sqrt5}{10}\right)\cdot\left(\frac{1+\sqrt5}{2}\right)^n+\left(\frac{5-3\sqrt5}{10}\right)\cdot\left(\frac{1-\sqrt5}{2}\right)^n$$ Calculate: $$f(n+1)-f(n-1)\\ ...
2
votes
1answer
24 views

Uniqueness of solutions to linear recurrence relations

I understand that if I have a linear homogeneous recurrence relation of the form $q_n = c_1 q_{n-1} + c_2 q_{n-2} + \cdots + c_d q_{n-d}$, I can construct the characteristic polynomial $p(t) = t^d - ...
3
votes
2answers
56 views

Solving combinatorical problem using characteristic polynomial

How many $6$ length strings above $\left\{1,2,3,4\right\}$ are there such that $24$ and $42$ aren't allowed. The suitable recurrence relation for this problem is: $a_{n+2} = 2a_{n-1} + ...
1
vote
2answers
29 views

Finding the inhomogeneous solution

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would I find the inhomogeneous solution for this since the homogenous solution is 0 given initial conditions?
1
vote
2answers
45 views
0
votes
0answers
13 views

Compact closed form for linear recurrence formulas

Assume you have some linear recursion formula $$f(\vec x)=\sum_{\vec y\in Y}w_{\vec y}f(\vec x - \vec y)$$ Where $\vec y\geq 0 $ and $||\vec y||>0$, $w_{\vec y}\in\mathbb{R}$ and $\vec x , \vec ...
0
votes
2answers
36 views

Help solving recursive relations

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would you solve this recursive relation? I have the homogenous solution, but am having issues with the ...
0
votes
2answers
41 views

Differentiate a recurrence relation

How do I calculate the derivative of an equation like: $z_n = (z_{n-1} + c)^2$ with respect to $n$ where $z_0 = 0$ and $z,c \in \mathbb{C}$ I suspect that, for a given $z$, the derivative is not ...
1
vote
1answer
61 views

Concerning a specific family of recursive sequences

There is a family of recursive sequences that I came up with: $$a_n=\text{sum of factors less than $a_{n-1}$ of } a_{n-1}, a_0\in\mathbb{N}$$ First question: Has it been studied before? Here are ...
0
votes
3answers
62 views

Are Pell solutions “unique”??

Given the Pell equation $$X^2-2Y^2=1$$ and two solutions $(x_j,2uv)$ and $(x_k,2ac)$, with $uv=ac$ and $\gcd(u,v)=\gcd(a,c)=1$ and $u>v$ and $c>a$. Can one prove that $(u,v)=(c,a)$, and hence ...
3
votes
2answers
72 views

Find the limit of the sequence given by recurrence relation

Find the limit of the sequence given by recurrence relation $c_{n+1} = (1-\frac{1}{n})c_n + \beta_n $ where $ \beta_n $ is any sequence with the property $n^2\beta_n \to 0$ as $ n \to \infty$ I've ...
2
votes
1answer
102 views

How can I make this recurrent equation non-recurrent?

I have a recurrent equation that defines a sequence $a_k$ from a sequence $b_k$: $$a_k = b_k - \sum^\infty_{i=k+1}a_i$$ How can I write this equation without mentioning $a_k$ on the right side?
0
votes
0answers
61 views

Recurrence equation analysis of the form T(x) = t + max{T(…) + …}

I want to find the worst-case running time of an algorithm I came up with, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where $$ ...
1
vote
0answers
24 views

What [precisely] is special, algebraically, about fundamental Pell solutions?

I'm asking for a list of algebraic identities which "uniquely identify" (or nearly so) the fundamental solution (or those immediately around it) of a Pell equation. As a concrete [numerical] example, ...
1
vote
0answers
70 views

Recurrence Relation Challenges

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
1
vote
1answer
18 views

Sequence of integrals defined by recurrence

For a sequence of integrals defined as follows $F_0(x)=f(x)$ for some function $f(x)$, $F_n(x)=\int_0^x F_{n-1}(y)dy$ for all $n\geq1$, can we use change of variables to find a nice expression for ...
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}) ...
1
vote
2answers
80 views

How do I find $\sum_{i=1}^n\frac{1}{x_i}$ where $x_i = x_{i-1} + \frac{1}{x_{i-1}}$

I have a recurrence: $x_n = x_{n-1} + \frac{1}{X_{n-1}}$. I need the value of n for which $x_n$ IS CLOSEST TO $2*x_0$, where $x_0$ is a positive integer. I tried the following: $x_1 = x_0 + ...
1
vote
0answers
34 views

Finite geometric sequence with a ratio greater than 1

I am trying to solve the recurrence relation: $ t(n)= 3T(n/2)+Cn$ (if $n>2$) $t(2)=C$ (otherwise) I know that there is the Master Theorem but I am trying to use the tree method. This ...
2
votes
1answer
31 views

Solving recurrence

Can anyone help me solving this recurrence? I don't see how I could use Master Theorem for this one and I couldn't find anything that would give me some idea how to do this. $$ T(n) = ...
1
vote
2answers
62 views

Counting numbers with the digit 5: How to express recurrence relation in closed form?

I figured out the algorithm for finding the count of numbers containing the digit 5 for any power of 10. What is the correct way to express y in this formula? $f(x) = 9y + (x/10)$ Where y is ...
0
votes
0answers
22 views

Functional Relationship Question on Analytic Geometry

I am solving some problems on analytic geometry. I have a set of points $\{P_1,P_2,P_3,...,P_k\}$ from wich $P_1,P_2$ are known. The rest have coordinates $P_n\big(x_n,y_n\big)$ and for any value of ...
5
votes
2answers
149 views

Let $x_{n+1} = x_n + 1/(x_1 + x_2 +\ldots + x_n)$ with $x_1 = 1$. Show that $x_n\sim\sqrt{2\log(n)}$.

As the title states we have a sequence defined by $$x_{n+1} = x_n + \dfrac{1}{x_1 + x_2 + \cdots + x_n}$$ with $x_1 = 1$. The first few terms are: $1, 2, \frac{7}{3}, \frac{121}{48} \cdots$ Any ...
0
votes
1answer
43 views

Problem with making explicit formula from recursive formula

I'm having trouble turning this recursive formula into explicit one $a_0 = 0,\\a_{n+1} = a_n(1 - b_n) + b_n,$ where $(b_n)$ is given sequence of real numbers.