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

learn more… | top users | synonyms (2)

0
votes
0answers
24 views

How to solve this kind of recurrence relation in closed form? $F(n) = aF(n-1) + bF(n-2) + cF(n-3) + dF(n-4)$

How to solve this recurrence relation in closed form? $$F(n) = aF(n-1) + bF(n-2) + cF(n-3) + dF(n-4)$$ I know how to solve recurrence relations for less than four calls by solving the ...
1
vote
1answer
27 views

Sum and product of linear recurrences

Given $a_n = \alpha_1 a_{n-1} + \cdots + \alpha_k a_{n-k}$ and $b_n = \beta_1 b_{n-1} + \cdots + \beta_l b_{n-l}$ are linear recurrences with complex coefficients, how can I find linear recurrences ...
3
votes
2answers
62 views

Closed form for solution of $t_{n+1}=t_n(t_n-2)$

As in the title I am interested in finding closed form for sequence satysfing $$t_{n+1}=t_n(t_n-2)$$ with $t_1=4$. I have tried many guesses, because I don't know if there is a metod to solve that, ...
0
votes
1answer
22 views

A closed form for the coefficients of Chebyshev polynomials

The Chebyshev polynomials are defined recursively: $T_0(x)=1$; $T_1(x)=x$; $T_n(x)=2xT_{n-1}(x)-T_{n-2}(x)$ I have been trying to find a closed form for the coefficient on the monomial $x^j$ of the ...
0
votes
1answer
32 views

Does the solution to $C_n = 2C_1 C_{n-1} - C_{n-2}$ can only be solved with $A = B = \frac{1}{2}$?

I was trying to solve the following recurrence in closed form (in terms of the initial conditions/base cases): $$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$ with base cases: $$ C_1 = C_1 $$ $$ C_2 = 2 C^2_1 ...
1
vote
1answer
49 views

Name of the numbers defined by $T(p,q) = T(p-1,q) + T(p,q-1)$?

I came across these numbers : $$ T(p,q)= \sum_{k=0}^{q-1} {p+k-1 \choose p-1} + \sum_{l=0}^{p-1} {q+l-1 \choose q-1} \quad p,q \in \mathbb{N} $$ While trying to solve this recurrence relation : $$ ...
2
votes
1answer
79 views

How to calculate the $n$-th member of sequence $a_{n+1}=\sqrt{y+a_{n}}$

I was searching for a smooth continuous concave function $$f:R^{+}\times R^{+}\to R^{+}$$ so that $$f(x+1,y)=\sqrt{y+f(x,y)}\quad\text{and}\quad f(0,y)=0.$$ But I couldn't find a general function, ...
0
votes
1answer
25 views

Find two linearly independent solutions of a Legendre equation about $x=0.$

Here is the statement of the problem: Consider the Legendre Equation $$ (*)\qquad (1-x^2)y''-2xy'+2y=0 $$ (a) Find two linearly independent solutions about $x=0$, solving completely any relevant ...
4
votes
0answers
54 views

How do i find formula for the recurrence relation :$x_{n+1}= x^2_{n}-x^2_{n-1}$ with :$x_{-1}=0,x_{0}=\frac{3}{4}$?

How do i find formula for the recurrence relation according to the below initial conditions: $x_{n+1}= x^2_{n}-x^2_{n-1}$ with :=$x_{-1}=0,x_{0}=\frac{3}{4}$ ? Note:$n=0,1,2\cdots$ Thank you for ...
4
votes
5answers
67 views

finding $a_1$ in an arithmetic progression

Given an arithmetic progression such that: $$a_{n+1}=\frac{9n^2-21n+10}{a_n}$$ How can I find the value of $a_1$? I tried using $a_{n+1}=a_1+nd$ but I think it's a loop.. Thanks.
0
votes
4answers
94 views

Limit of $\{a_n\}$, where $a_{n+1} = \sqrt{2+a_n}$ [on hold]

I am struggling with this question: Let $\{a_n\}$ be defined recursively by $a_1=\sqrt2$, $a_{n+1}=\sqrt{2+a_n}$. Find $\lim\limits_{n\to\infty}a_n$. HINT: Let $L=\lim\limits_{n\to\infty}a_n$. ...
1
vote
1answer
47 views

Find recursive formula - Question from exam, check my answer

We want to demolish and move a bridge from one location to another. The bridge is made out of $m$ road segments all connected $[0,1]$, $[1,2]$, $[2,3]$...$[m-1,m]$ We have a given function $f$ which ...
1
vote
1answer
27 views

Lines in the plane from Concrete Mathematics. How many bounded regions are there?

I'm studying Concrete Mathematics by Donald Knuth. While doing the warmup questions, from the recurrence chapter, I stumbled upon an interesting problem. I have an intuition about the solution but I ...
3
votes
2answers
226 views

Can the recurrence $C_n = 2 C_1 C_{n-1} - C_{n-2}$ be expressed in a closed expression?

I was wondering if the expression: $$ C_n = 2 C_1 C_{n-1} - C_{n-2} $$ could be expressed as a closed expression in terms of (hopefully polynomials of) $C_1$ (or $C_2$). The bases cases for this ...
1
vote
1answer
17 views

Recursive Equation : $X_t=-\sum_{j=1}^{\infty}\phi^{-j}W_{t+j}$

$X_t=\phi X_{t-1}+W_t$ $\Rightarrow X_{t-1}=\frac{1}{\phi} X_{t}-\frac{1}{\phi}W_t$ Where , $|\phi|>1$ . But how does the following recursion relation occur : ...
4
votes
2answers
215 views

Recursive sequence of square roots of previous elements

Bruckner, Bruckner, Thompson - Elementary Real Analysis $a_1 = 1$ and $a_{n+1} = \sqrt{a_1+ a_2 + .. + a_n}$ Show that $$\lim_{n \to \infty}\ \frac{a_n}{n} = \frac12$$ I cannot untangle the square ...
1
vote
3answers
55 views

showing the limit of a recurrence relation

The recurrence relation is defined as such: $$a_n=2+\frac{80}{a_{n-1}}$$ It is also given that $a_1=2$, how do we show that $$\lim_{n\to\infty}a_n=10 ?$$ I am totally stuck at how I should approach ...
0
votes
1answer
11 views

Recursive formula for minimal editing distance - check my answer

Given a word $X=x_1x_2x_3...x_i$ and $Y=y_1y_2y_3...y_j$, the minimal editing distance is defined to be the minimal number of actions needed to transform $X$ to $Y$ where the legal actions are: 1) ...
0
votes
1answer
48 views

Tiling problem : Number of ways a floor can be tiled

Find number of ways a floor n meter length and 11 meter wide can be floored with tiles of 2 cm length and 1 cm wide wide tiles without breaking the tiles (assume n is even) Could you please help in ...
0
votes
1answer
14 views

Recurrence Relations with ternary strings

Find and solve a recurrence equation for the number gn of ternary strings of length n that do not contain 102 as a substring. I am having some trouble finding the recurrence relation for this ...
2
votes
3answers
41 views

Finding an explicit formula for a recursive sequence. [closed]

How to show that the recurrent formula $$A_n=A_{n-1} + A_{n-2} +4.$$ gives a sequence of the form $f(n)=cr^n+cr^n$? The only way we are allowed to solve it, is with the quadratic formula ...
2
votes
1answer
29 views

Find recursive formula for special function

Kind of a strange question I know, but here goes: We are given a string of letters $T$ without any gaps or commas, just letters. Depending on what $T$ is, it could be broken down to form a valid ...
1
vote
0answers
36 views

solving a linear recurrence relation simple moving average

Here's a recurrence relation, $k$ is fixed: $$\frac{1}{k}\sum_{n=i}^{k+i-1} a_n = a_{k+i}$$ for all $i\in \mathbb{N}$, and for $a_i$ with $1\leq i \leq k$ we have fixed non-negative real number ...
1
vote
2answers
56 views

Solving recurrence using analogy with continuous $x_{n+1} = \frac{r^2}{2d - x_n}$

What's up lovely friends, I'm facing a physics problem and felt on a recurrence that one does not see everyday. This one: $x_{n+1} = \frac{r^2}{2d - x_n}$ or $f(n+1) = \frac{a}{b-f(n)}$ if you will ...
2
votes
0answers
26 views

Solving this recurrence relation representing constant-power loads on a resistive cable

Given the following: $$\begin{align} v_n&=v_{n-1}-r\sum_{i=n}^m \frac p{v_i}\\ v_0&=V \end{align}$$ where: $$\begin{align} m\ge n\ge 0\;&:\;m,\,n\in\mathbb {N_0}\\ ...
5
votes
3answers
141 views

Prove that $A_{100} \gt 14$ where $A_{n}=A_{n-1}+\frac{1}{A_{n-1}}$ and $A_1=1$

I tried attempting the question, and the best upper bound I could obtain was $1+\ln{98}$. I tried using $A_{n}\le n$ to form a harmonic series, but that wasn't strong enough. Any help would be ...
3
votes
1answer
25 views

Solving recurrence relation with repeating roots

I am aiming to solve this recurrence relation and I have chosen the Characteristic Equation method: $d_n = 4(d_{n-1}-d_{n-2})$ with $d_0 =1, d_1=1 $ Finding the C.E. I get: $x^2-4x+4=0$ Solving for ...
0
votes
2answers
25 views

Recurrence relation complexity

I just learned about recurrences and I just can't solve this problem. I have this recurrence relation: $T(n)=k * T(n / k)$ $T(0)=1$, where k is a constant number. I tried drawing a recurrence tree ...
8
votes
2answers
149 views

Finding closed form for a generating function with different powers of $x$ in parameter

I'm working on a math/programming puzzle that involves an integer series defined as having a recurrence relating values $a(n)$ to $a(\lfloor\frac{n}{2}\rfloor)$ and $a(\lfloor\frac{n}{4}\rfloor)$. ...
2
votes
1answer
23 views

Are there variants (described below) of $3n + 1$ conjecture where the answer is known?

The $3n + 1$ conjecture states that if you take any natural number $n_j$, and if it is even then set $n_{j+1} = n_j/2$, otherwise set $n_{j+1} = 3n_j + 1$, then no matter what natural number $n_0$ you ...
2
votes
2answers
59 views

Product of Matrices I

Given the matrix \begin{align} A = \left( \begin{matrix} 1 & 2 \\ 3 & 2 \end{matrix} \right) \end{align} consider the first few powers of $A^{n}$ for which \begin{align} A = \left( ...
0
votes
2answers
51 views

How can I prove if these are (or not) possible solutions for the following recurrence?

So I'm presented with no initial conditions and the following recurrence relation: $8a_{n+2}+4a_{n+1}-4a_n=0$ I need to determine if these can are possible solutions, and if they are, which initial ...
0
votes
3answers
31 views

Showing that a series solves a recurrence relation

Let: $a_n = a_{n-1}+2a_{n-2} +3\cdot 2^n$, $\displaystyle b_n=4\sum_{k=0}^nk\binom n k$ Show that $b_n$ solves $a_n$ There are no starting conditions for the recurrence, that is how the ...
2
votes
1answer
26 views

Can You Help With This Tent Map Proof?

The question: Show that if $ x= \frac{k}{2^{n}}$ where k and n are positive integers with $ 0 < \frac{k}{2^{n}} <1 $, then x is eventually a fixed point of the tent map. My Attempt: If you ...
1
vote
1answer
24 views

Evaluation recursive limit

How to evaluate this limit: $\lim_{x\to0^+}\dfrac { -1+\sqrt { \tan(x)-\sin(x)+\sqrt { \tan(x)-\sin(x)+\sqrt { \tan(x)-\sin(x) } +...\infty } } }{ -1+\sqrt { { x }^{ 3 }+\sqrt { { x }^{ 3 }+\sqrt ...
0
votes
1answer
35 views

Recurrence relation for a string over the letters $\{A,B,C,D\}$ such that each $A$ appears before $C$

Find a recurrence relation for the number of strings of length $n$ that's composed of the letters $\{A,B,C,D\}$ such that each $A$ appears before $C$. $a_n=\begin{cases} A\text{______} = a_{n-1} ...
6
votes
2answers
64 views

How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$, if $a_0=0$ and $a_{n+1}=a_n+\sqrt{a_n^2+1}$?

Let $a_1,a_2,..,a_n$ be sequence of real numbers such that $a_{n+1}=a_{n}+\sqrt{1+a_n^2}$ and $a_0=0$. How to evaluate $\lim_{ n\to \infty }\frac{a_n}{2^{n-1}}$ ?
0
votes
2answers
51 views

Solving $g(n)=2g(n-1)+n+2^n$

I am learning how to solve recurrence relations and I have an equation that got me to a dead end: $$g(n)=2g(n-1)+n+2^n$$ My problem is the non-homogeneous part.
0
votes
0answers
26 views

Can recurrences involving $\gcd$ be solved?

Can recurrences of the form $$ \sum_{i=1}^n a_iX_i=\gcd(n, X_n) $$ Where $a_i$ are constant coeficients. $a_i,X_i$ are integers. $a_n\neq0$. For $n \geq 2$ be solved? Here is an example: $$ ...
1
vote
2answers
32 views

Find $r$, given that $F_r= 2F_{101}+F_{100}$

Find $r$, given that $F_r= 2F_{101}+F_{100}$. We know that the recurrence relation for the Fibonacci sequence is $F_n= F_{n-1}+F_{n-2}$ and that $F_0 = F_1 = 1$, but how to proceed further?
0
votes
2answers
40 views

Find coefficient of $X^{12}$

I need to find coefficient of $X^{12}$ in $({1-2X})^{19}$. What is the formula to solve it?I only know about $$\frac{1}{a-X}=\frac{1}{a}\sum_{r=0}^\infty \frac{X^r}{a^r}$$ ...
0
votes
1answer
15 views

Recurrence relation for ways to color a circle with two colors such that there can't be two adjacent reds

Find the recurrence relation for how many ways there are to color a carousel with a circumference of length $n$ with two colors, red and blue such that no two reds will be adjacent This is like ...
0
votes
0answers
26 views

this function is known ?: $h_{n+1}(x)=h_n(x)^2+h′_n(x)$

Let $f(x)=x^{1/x}$, so the first derivative of $f(x)$ is $f′(x)=f(x)∗(1−ln(x))/x^2$, and in general, $f^n(x)=f(x)∗h_n(x)$, where $f^n(x)$ is the nth derivative of $f(x)$. I was trying find this ...
1
vote
1answer
35 views

Solving the recurrence $T(n) = \sqrt n T(\sqrt{n}) + \sqrt{n}$

A former student of mine was TA-ing an algorithms class last quarter and asked students to solve this famous recurrence relation: $$T(n) = \sqrt n T(\sqrt{n}) + n$$ There are several ways to solve ...
0
votes
0answers
31 views

Solving a Recurrence for a Mathematical Game

The problem is: Two players take turns removing coins from a pile. There are initially $n$ coins, and on each turn, a player can remove $a_1, a_2, \dotsc, a_k$ coins. The player who cannot remove ...
0
votes
1answer
36 views

Can You Help Me With This Logistic Difference Equation?

In population biology, the following equation is the Pielou Logistic Equation, is used to model population with non-overlapping generations $$x_{n+1} = \frac{\alpha x_{n}}{1+\beta x_{n}}$$ Show ...
1
vote
0answers
22 views

FSR function of the component-wise product, sum, of two LFSR sequences

Let $T_1$, $T_2$ be two $m$-sequences over $\mathbb{F}_q$ of length $q^n-1$, say $T_1 = (\text{Tr}_{q^n | q}(\alpha^i))_{i \geq 0}$, $T_2 = (\text{Tr}_{q^n | q}(\beta^i))_{i \geq 0}$, for some ...
0
votes
1answer
22 views

Find the asymptotic tight bound for $T(n)=T(n-1)+n lg n + n$ and for $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$

I am stucked at this problem: Find the asymtotic tight bound for the following recurrences: (Assume that $T(n)$ is constant for sufficiently small $n$) (1) $T(n)=T(n-1)+n lg n + n$ (2) $T(n)=n^2 ...
1
vote
4answers
38 views

Computing good bounds for $P(n) = n + nP(n-1)$

What is the technique of computing the following recurrence? $$P(n) = n + nP(n-1)$$ (We assume $P(1) = 1$.) It is obvious that the lower bound for $P(n)$ is $n!$, and the upper bound is $(n+1)!$, ...
4
votes
0answers
171 views

Has this difference equation :$x_{n+1}=Ax^2_{n}-Bx^2_{n-1}$ been studied before?

I posted this problem before in MO but only I would like to know if this difference equation :$$x_{n+1}=Ax^2_{n}-Bx^2_{n-1}$$ where $A(\theta)= \cos(\theta)$ and $B(\theta) =\sin(\theta)$ are ...