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

learn more… | top users | synonyms (2)

0
votes
1answer
8 views

How to find the generating function from recurrence relation $t_n=(1+c~q^{n-1})~p~t_{n-1}+a +b+nbq, ~~n\ge 2$?

How to find the generating function $T(z)=\sum_{n=0}^{\infty} t_n~z^n$ from the recurrence relation $$t_n=(1+c~q^{n-1})~p~t_{n-1}+a +b+nbq,\qquad n\ge 2.$$ given that $$t_1=b+(1+c~p)(a~q^{-1}+b),$$ ...
0
votes
3answers
22 views

Simple Linear Recurrence Relation Problems

$M(n)=3M(n−1)+1$ with base case of $M(1)=1$ Somehow I'm not understanding how to solve the recurrences. This problem is from my textbook and I was fine until I see this in example. I know it goes ...
1
vote
1answer
19 views

Linear recurrences relation

These are from my textbook examples, introduced as Theorem 1, If $T(n)=rT(n-1)+a,$ $T(0)=b$ and $r\ne 1$, $T(n)=r^nb+\left[\frac{a(1-r^n)}{(1-r)}\right]$ And I supposed to solve other ...
-2
votes
2answers
32 views

Summation Problems

How did this particular equation come about? I haven't seen it before in the summation rules index on wikipedia: $$\sum\limits_{i=1}^{k+1} x_i =\left(\sum\limits_{i=1}^{k} x_i\right)+x_{k+1} $$
0
votes
1answer
64 views

How can I solve this recurrence problem?

Given a function $$ f(n) = f(5n/13) + f(12n/13) + n \;\;\;\;∀n \geq 0 $$ I would like to find a function $g(n)$ such that $f ∈ Ө(g(n))$.
2
votes
1answer
42 views

Recurrence relation involving infinite sequences.

How in general one would solve an infinite series recurrence relations? For instance, I am interested to solve the following: \begin{equation} \sum_{n=0}^{\infty} (-1)^{n} F(n)\{1-(\alpha n ...
0
votes
0answers
9 views

Simpler proof of Karp's Theorem for probabilistic recurrence relations?

A probabilistic recurrence relation is of the form $T(x) = a(x) + T(h(x))$ with $a(x)$ deterministic (usually $a(x) = 1$) and $h(x)$ being a random variable over $[0,x]$, so that $T(x)$ itself is a ...
0
votes
1answer
28 views

Recurrence involving square root

The recurrence equation I have is: $$ T_n = c_1 + T_{n-1} + 2\sqrt{c_2 + c_1 T_{n-1}} $$ $$ T_0 = a $$ $c_1,c_2,a$ are positive real numbers I need to somehow convert this into a linear homogeneous ...
0
votes
1answer
25 views

Number Theoretic Sum of three variables. Having trouble isolating two of them.

I encountered the following sum: $$\frac{c_{mn-p}}{c_0} = \sum_{d|p}\ \frac{a_{n-d}b_{m-\frac{p}{d}}}{a_0b_0} $$ Where $$a_i=0 \text{ when } i<0 \text{ and } b_j=0\text{ when } j<0\text{ and ...
0
votes
0answers
34 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
32 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
64 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
33 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
50 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
83 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
27 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
57 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
96 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
229 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
216 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
49 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
1answer
150 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
65 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
41 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}$$ ...