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

learn more… | top users | synonyms (2)

1
vote
0answers
16 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
1answer
1k views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
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
4answers
47 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.
3
votes
2answers
61 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, ...
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, ...
1
vote
1answer
48 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 : $$ ...
0
votes
1answer
31 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 ...
0
votes
1answer
21 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
4answers
93 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$. ...
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 ...
2
votes
0answers
63 views

Validity of approximating a difference equation with a differential equation

Consider the following two equations: $$ \begin{cases} A_k(n+1)-A_k(n)=\beta \displaystyle \frac{ A_{k-1}(n)- A_k(n)}{\alpha+ n} + \delta_{k, \beta} \\ \\ \displaystyle ...
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 ...
2
votes
1answer
339 views

How to find a closed form formula for the following recurrence relation?

I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm - $$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with ...
1
vote
1answer
46 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 ...
2
votes
1answer
83 views

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
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 ...
8
votes
2answers
147 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)$. ...
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
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) ...
1
vote
2answers
449 views

Find recurrence relation for ternary strings that don't have substrings 00, 01 and last symbol is not 0

I am preparing for my finals for discrete mathematics and I came across this exercise in textbook. Let $s_{n}$ denote all ternary strings of length $n$, such that any string in $s_{n}$ does not ...
5
votes
3answers
140 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 ...
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 ...
4
votes
3answers
4k views

Linear Algebra: Finding a steady state matrix

Here is the problem: And here is what I tried to do: I tried doing it in my calculator and got that the answer is 40 and 160 as you keep multiplying PX. Can anyone point out what I'm doing wrong ...
4
votes
3answers
2k views

Recurrence relation (linear, second-order, constant coefficients)

Q1. Find the general solution to the difference equation $$ a_{n} - 4a_{n-1} + 3a_{n-2} = 6 $$ Q2. Solve the difference equation $$ a_{n} - a_{n-1} - 2a_{n-2} = 0, a_0 = 2, a_1 = 4 $$ I am ...
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 ...
-2
votes
2answers
872 views

A recurrence relation problem involving intersecting circles?

Respected Sir, Please give a complete information about the following one: Find a recurrence relation for the number of regions created by 'n' mutually intersecting circles on a piece of paper (no ...
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 ...
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 ...
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}\\ ...
0
votes
3answers
50 views

Prove that the elements of these two sequences are not null

Let $x_{n+1}=x_n+2y_n$ and $y_{n+1}=y_n-x_n$, where $x_1=1$ and $y_1=-1$. I tried proving by contradiction, I tried by induction, I got nothing. This is a question I had on an exam, I didn't manage ...
3
votes
1answer
457 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 ...
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 ...
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 ...
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
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 ...
22
votes
0answers
517 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
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 ...
9
votes
3answers
233 views

Quadratic Equation Recurrence?

So I was playing around with the following: Let $f_0(x) = x^2 - bx + c$. If $f_n(x)$ has roots $p$ and $q$ with $p > q$, then let $f_{n+1}(x) = x^2 - px + q$. The recurrence relation is rather ...
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 ...
5
votes
1answer
125 views

How can I show that the sequence $x_n^2$ is bounded?

Two real sequences $(x_n)$ and $(y_n)$ are defined by $$x_{n+1}=x_n-(x_ny_n+x_{n+1}y_{n+1}-2)(y_n+y_{n+1})$$ $$y_{n+1}=y_n-(x_ny_n+x_{n+1}y_{n+1}-2)(x_n+x_{n+1})$$ with initial conditions $x_0=1$ and ...
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} ...
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: $$ ...