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

learn more… | top users | synonyms (2)

0
votes
0answers
16 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)^2y''-2xy'+2y=0 $$ (a) Find two linearly independent solutions about $x=0$, solving completely any relevant ...
4
votes
0answers
45 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
3answers
34 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.
1
vote
1answer
45 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
202 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
16 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
211 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
53 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
13 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. [on hold]

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
25 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
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 ...
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 ...
-1
votes
2answers
32 views

Maximum of the solution of the difference equation $B_{n+1}=0.9B_n +3$ with $B_1=5$ [closed]

I'm revising for a SAC and need help with question B.III I don't know how to find the maximum charge, can someone help me please. I need it fast :) thanks!
8
votes
2answers
125 views
+150

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
25 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
23 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
31 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
34 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
30 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
118 views
+50

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 ...
1
vote
2answers
36 views

Linear Recurrence Problem

$f(0)=3, f(1)=1, f(n)=4f({n-1})+21f({n-2})$ Thought linear recurrence problems usually have subsets of things, and this seems like a new type for me. Can anyone help me out with hints?
2
votes
2answers
35 views

Help with recurrence $T(n) = T(n/2) + n$

I just need help seeing where I went wrong in this solution. $$T(n) = T\left(\frac{n}{2}\right) + n,~~~ T(1) = 0$$ By master theorem, this is $\theta(n)$. However, when I try to solve it, it ...
0
votes
2answers
45 views

Please help to find the formula for a relation

I'm trying to find the formula for the following relation: $ x_1 + x_2 + x_3 + x_4 = n $ where: $ 0 \leq x_1 \leq 3$ $ 0 \leq x_2 \leq 3$ $ x_3 \geq 0 $ $ x_3 \geq 0 $ Let $a_n$ be the ...
0
votes
0answers
28 views

How to predict intuitively the recurrence relations of josephus problem?

i have studied the Josephus problem from the concrete mathematics book.I have understand all related calculations discussed on that book.However i have some difficulties regarding to recurrence ...
0
votes
2answers
59 views

Finding a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in

Find a recursive formula for a string of the letters $A,B,C$ such that $AB, BC$ does not appear in. $a_n=\begin {cases}A\text{____}a_{n-1}\\ B\text{____}a_{n-1}\\ C\text{____}a_{n-1}\\ ...
1
vote
1answer
43 views

Maximum nodes in AVL tree with distinct positive integers

Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ? We ...
1
vote
4answers
35 views

Proving recurrence by mathematical induction

$f(1)=1,$ $f(n)=2f(n-1)+3$ ($\forall n>1$) has the following closed form solution $f(n)=2^{(n+1)}-3$ I understand that I can simply show that the recurrence is equal to $2^{(n+1)}-3$,but not ...