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

learn more… | top users | synonyms (2)

1
vote
0answers
33 views

solving a two variable recurrence

i have the following two variable recurrence: $$f(i,n+1) = f(i-1,n)*\frac{n-i+1}{n} + f(i,n)*\frac{i}{n}$$ $$f(0,n) = (\frac{1}{n})^{n-2}$$ $$f(i,0) = 0$$ I'm not sure which method can I try to ...
0
votes
1answer
27 views

finding number of subsets so that there are no two consecutive numbers in them

I already had a look at the following problem: For a given set $\{1, \dots, n\}$, how many sets are there so that there are no two consecutive numbers in them? The answer could be found by using ...
1
vote
1answer
24 views

How to solve this nonlinear difference equation $y_{t+1}-y_{t}+ty_{t+1}y_{t}=0$

I need help to solve the following difference equation: $$y_{t+1}-y_{t}+ty_{t+1}y_{t}=0$$ I start by dividing with $y_{t+1}y_{t}$. Then I get: $$y_{t}^{-1}-y_{t+1}^{-1}=-t$$ Then I assume ...
2
votes
3answers
122 views

Evaluating an infinite sum involving possibly hypergeometric terms

I was considering the following infinite sum $$ A(n) = \sum_{k=2}^{\infty}\left[\frac{(-1)^{k+n-1}}{k^n}(0k -1)(k-1)(2k-1)...((n-1)k-1) \right] $$ Some cases: $$ A(1) = ...
1
vote
1answer
42 views

Solving recurrence relation $a_{n+1} = \frac{3a_n^2}{a_{n-1}}$

I am currently studying recurrence relations and I am stuck at a particular problem: $$a_{n+1} = \frac{3a_n^2}{a_{n-1}}$$ for $n \geq 1$, starting with $a_0 = 1$, $a_1 = 2$. In the lecture, we only ...
0
votes
0answers
20 views

Solving a Quadratic Recurrence Relation of Degree 3

Given $ 0<a,b,y,s \le 1$ Let $U_0=u_0$, $U_1=u_1$ and $U_2=u_2$, and let $T_n= \frac{(1-y)(a^2-b^2)}{2 s^2 b^2}U_n^2$ How to find the closed form for the following recurrence relation? ...
0
votes
1answer
46 views

Master theorem. Particular example I can't understand

I thought that I understood how to use the Master Theorem but apparently I don't. So here it is: ...
-1
votes
1answer
59 views

For what values $\alpha$ does the iteration of $e^{-\alpha x}$ converge?

For what values of $\alpha >0$ will the fixed point iteration $x_{k+1} = g(x_k)$ converge for $g(x)=e^{-\alpha x}$ assuming that $x_0= [0,1]$. Would it suffice to find the derivative of say ...
0
votes
1answer
49 views

Recurrence relation of number of sequences with $0,1$ and $2$

$d_n$ represents number of sequences of length $n$ made by $0, 1$ and $2$ that don't contain two consecutive 1 or 2. for example $d_2 = 7$ because valid sequences are $\{00,01,02,10,12,20,21\}$. first ...
0
votes
3answers
38 views

Closed form solution for the recurrence

I am given the following recurrence and need to find a closed form solution for the recurrence. I have no idea on how to get started though and i need some help on leading me to solve this. $A_0=20, ...
0
votes
0answers
20 views

What many associative ways are possible an expression of n variables? [duplicate]

Let's say we have an expression AxBxC and x is associative. Then we can solve it as (AxB)xC or Ax(BxC) i.e 2 ways, similarly for 3 variables, I found 5 ways. How can we find a general formula for n ...
4
votes
3answers
143 views

$n$-words over the alphabet $\{0,…,d\}$ without consecutive $0$'s

I'm trying to solve the following problem in chapter 3 of Aigner's A Course in Enumeration: Let $f(n)$ be the number of $n$-words over the alphabet $\{0,1,2\}$ that contain no neighboring 0's. ...
0
votes
0answers
28 views

Non-homogeneous recurrence relation problem with $n\cdot 3^n$

I have a problem with finding the general solution for this non-homogeneous recurrence relationship: $$a_{n}=4a_{n-1}+5a_{n-2}+n\cdot 3^{n}$$ I solved the homogeneous part, but I honestly don't now ...
1
vote
0answers
29 views

Relation by induction

Suppose we have the element $a$ and $b$ in some algebra $A$ and $0<q<1$ subject to the relations: $$a^2b-(q+q^{-1})aba+ba^2=0$$ $$b^2a-(q+q^{-1})bab+ab^2=0$$ I want to deduce from this a ...
1
vote
0answers
96 views

Show that $T(n) = 4 × T (n - 1) - T(n-2)$…

$T(n)$ is the number of spanning trees for the n-ladder. Show that $T(n) = 4 × T (n - 1) - T(n-2)$. -My teachers hint was to first show $T(n) = 3×T(n-1) + 2×T(n-2) + 2 × T(n-3) + ... + 2× T(2) + 3 × ...
0
votes
1answer
14 views

Uniqueness of a solution class for a homogeneous recurrence equation

I have a homogeneous recurrence equation. $x_i = (1-p)x_{i-1} + px_{i+1}, p \in (0,1)$ Using the classical methods (solving the characteristic polynomial) I can show that if $p=1/2$, then the ...
1
vote
3answers
34 views

$F(x) = .5 F(x+1) + .5F(x-1)$.. How to solve

I saw this in an mit open courseware video for approximating the probability of Reaching one value versus another in a coin flip game. For example, if $f(10) = 1$ and $f(-5)=0$ what is $f(0)$ (you ...
1
vote
1answer
29 views

Solving the system of recurrence relatioin

Given the recurrence system: \begin{equation*} \begin{cases} T_n = T_{n-1} + S_n, &\\ S_n = T_{n-1} + S_{n-1} & \end{cases} \end{equation*} And we know $T_0 = 1, S_0 = 0$. I tried to ...
0
votes
1answer
26 views

A way to solve the recurrence relation $T_i = T_{i-1} + 2 T_{i-2} + 2^{i - 2} - (i - 2)^2$

Given the recurrence relation $$ T_i = T_{i-1} + 2 T_{i-2} + 2^{i - 2} - (i - 2)^2,\quad T_0 = 0,\quad T_1 = 1. $$ I need to solve it. I tried to solve the relation using generating function, but ...
0
votes
3answers
45 views

problem in solving recurrence relation

I'm not able to find particular solution of $a_n-2a_{n-1}$=$3*2^n$ What i've tried Given RR is $a_n-2a_{n-1}$=$3*2^n$ For the particular solution observe the r.h.s of the equation(1) It is ...
0
votes
1answer
29 views

Divide and Conquer Recurrence Relation

I have this Divide and Conquer relation and I need to provide recurrance relation of it. I got something like $T(n) = 4T(n) + \lfloor\frac{n}{2}\rfloor$ but still confused whether this is right ...
2
votes
0answers
36 views

What is the solution to this recursion?

Take $a_0=10^6$. What is $a_n$ (asymptotically) where $a_{i+1}=a_i+\sqrt[\alpha]{a_i}$ where $\alpha>1$? How fast does $a_n$ grow?
1
vote
0answers
33 views

Show that these two identities are equivalent

As an answer to the question Proof that for $a>0$ and $a + 1/a$ element of $\mathbb{Z}$, $a^n + 1/a^n$ is always element of $\mathbb{Z}$ by induction, user236182 gave this answer: ...
0
votes
2answers
20 views

Closed form for a certain recurrence relation

Can anybody give me a closed form for the (limit of the) recurrence relation $a_0 = 0$, $a_{n+1} = \frac 1 2 \cdot \big(1 + (a_{n})^2\big)$? And more general: Can anybody give me a closed form for ...
1
vote
1answer
62 views

Solving a tricky recurrence relation

Given the following recurrence relation: $T_2=1$ $T_4=4$ $T_{2n}= \begin{cases} T_{2n-2}+3\bmod2n & 2T_{2n-2}\geq2n-2\\ T_{2n-2}+2\bmod2n & 2T_{2n-2} < 2n-2\\ \end{cases} ...
1
vote
5answers
38 views

Solving non-homogeneous recurrence relations of type $a_{n+1} - a_{n} = c_{_1}n+c_{_2}$

I do not understand how to go about solving the following form of non-homogeneous recurrence relations; $a_{n+1} - a_{n} = c_{_1}n+c_{_2}$. I have the following question: $a_{n+1} - a_{n} = 2n+3$ ...
2
votes
1answer
27 views

Homework help with Non-homogeneous Recurrence Relations

I solved this problem but am not super confident with my methods, if someone could take a look at it and tell me if it looks okay, that would be great. Solve the following non-homogeneous recurrence ...
2
votes
1answer
13 views

Solve the following homogeneous recurrence relation

$a_n=2a_{n-1}-a_{n-2}$ $a_{0}=a_{1}=2$ $x^{2}=2x-1$ $x^{2}-2x+1=0$ $(x-1)^2=0$ $x=1$ $a_{n}=(α+βn) 1^{n}$ $(α+β(0)) 1^{0}=2$ $α=2$ $(α+β(1)) 1^{1}=2$ $α+β=2$ $a_{n}=2$ I can't seem to find ...
2
votes
6answers
131 views

Limit of a recursive sequence with an independent term that goes to 0

I have a recursive sequence where the first element is $a_{1} = 1$ and then $a_{n+1}= \frac12a_{n} + \frac{1}{n+1}$. The first three terms are $a_{1} = 1 > a_{2} = \frac56 > a_{3} = \frac23$ so ...
0
votes
2answers
56 views

Limit of a sequence given by $x_n = \sqrt{3 + x_{n-1}}$ as n approaches infinity [closed]

Let $x_1 = 1$ and for $n \ge2, x_n = \sqrt{3 + x_{n-1}}$, I just want to know how to determine the limit.
1
vote
1answer
30 views

Solution to closed form of a Generating function

Can anyone give me the closed form of the generating function $$\Sigma ^\infty_{r=2} r.4^r.x^r$$ I am trying to solve recurrence relation using generating functions and this is one of the terms. I ...
0
votes
0answers
33 views

Differential Equations

I was solving the 2nd order Bessels's equation. I got till the point where I found the roots of the indicial equation. They were 2, -2. I got the Frobenius series expansion for the series associated ...
0
votes
3answers
114 views

Solving A Linear Recurrence Relation With Complex Roots

Question: For the given linear homogeneous difference equation, find the general solution: $$y_{n+2} + y_{n+1} + y_n = 0$$ With the initial conditions of: $$y(0)=\sqrt3, y(1) = 0$$ Attempted ...
0
votes
1answer
22 views

Solution of the recurrence relation

How can we solve the following recurrence relation? $$f_n=\left (\frac{2}{a^2}+b\right )f_{n-1}-\frac{1}{a^4}f_{n-2} \\ f_0=1, f_{-1}=0$$ I calculated some values to see if there is a general ...
2
votes
0answers
52 views

Can anyone identify the orthogonal polynomial for this recurrence relation?

I have come across this recurrence relation: \begin{equation} x p_n(x) = (N - n)(n + 1) p_{n+1}(x) + (N - n + 1) n p_{n - 1}(x) \end{equation} with $p_{-1}(x) = p_{N + 1}(x) = 0$. I expect $p_n(x)$ ...
0
votes
1answer
14 views

Having trouble with the general term of recurrence relation $g(j+1) = a g(j) + bg(j-1)$ with boundary conditions

I am trying to understand the general term of following recurrence relation I rewrote it as: $$g(j) = e^{-h}[p g(j+1) +q g(j-1)] $$ which yields: $$ g(j+1) = \frac{e^h}{p} g(j) - ...
1
vote
3answers
72 views

Recurrence Relation $T_n=\sum_{r=0}^{n-1} T_r+2^n$

From a recent solution I posted here, working from an alternative path would have led to the following recurrence relation which involves a summation term: $$T_n=\sum_{r=0}^{n-1}T_r+2^n; \qquad ...
-1
votes
1answer
36 views

The recurrent sequence $u_{n+1}=u_n+a_n/u_n$ is convergent if and only if $\sum a_n$ is finite

Let $u_0 > 0$ be a real number and let $(a_n)$ be a sequence of strictly positive real numbers. Define the sequence $(u_n)$ by : $u_{n+1} = u_n + (a_n/u_n)$ 􏰀 Show that $(u_n)$ is convergent if ...
1
vote
2answers
82 views

Write a recursive definition for the set of all binary strings that contain an odd number of zeros, and for all that end with a 0.

I am trying to do two things. Write a recursive definition for the set of all binary strings with an odd number of $0$s. Write a recursive definition for the set of all binary strings that end with ...
1
vote
1answer
55 views

Difference equation (Discrete time) to Differential Equation (Continuous time)

Suppose I have the following difference equation \begin{equation} v(t+2) + a v(t+1) + b v(t) = 0. \end{equation} I wish to convert it to a second order ODE. How does one go about doing this? (note: ...
0
votes
2answers
49 views

Finding a closed form for the recursively defined function using the substitution method.

This is a question from a problem set I had to do for one one of my courses. The following recursively defined function is given \begin{equation*} T(n) = \begin{cases} 1, & if \ n=0 \\ 4, & ...
1
vote
2answers
39 views

Finding the particular solution to the following non-homogeneous recurrence relation

$$x_n = 2x_{n-1}+2^n$$ $$x_1 =5$$ Finding the homogenous solution is easy enough but when attempting to solve the particular solution I arrive at: $$C_22^n = 2C_22^{n-1} + 2^n $$ $$2C_2 = 2C_2 + 2 ...
1
vote
1answer
65 views

Use a divide and conquer algorithm to find f(n)

Use $f(1) = a$ and $f(n) = 3f(n/2) + bn$ to show that $f(n)= a(3^m) + 2(b)(3^m) - b(2^{m+1})$. Also note that $n=2^m$ Using the recurrence relation: $f(n)= a^m (f(1)) + \sum_{i=1}^{m} ...
2
votes
4answers
97 views

Find $f(x)$ if $\Delta f(x)=e^x$

Find $f(x)$ if $\Delta f(x)=e^x$, where $\Delta f(x)$ is the first order forward difference of $f(x)$, step size $=h=1$. Attempt: We have the definition $\Delta f(x)=f(x+h)-f(x)=f(x+1)-f(x)$ ...
0
votes
1answer
46 views

How to solve $n^{th}$ determinant in complex domain using recurrence relations?

If $D_n=pD_{n-1}+rD_{n-2},n\ge 3$ is recurrence relation with constant coefficients, If $r=0\Rightarrow D_n=p^{n-1}D_1$ If $r\neq 0$ then solve equation $x^2-px-r=0$ If $$\Delta>0\Rightarrow ...
0
votes
1answer
24 views

stability differential vs difference equations

Consider the differential equation $\dot{x} = \sin x$. The stability and dynamics of this equation has been discussed thoroughly in Nonlinear Dynamics and Chaos by Strogatz. If I change the equation ...
0
votes
2answers
42 views

Recurrence relation. Why subtitute $A_{n} = cr^{n}$ for second order homogeneous recurrence?

Recently I learned about recurrence relation and I understand the general solution for first order homogeneous recurrence relation is $A_{n} = cr^{n}$. But why do we substitute that for second order ...
1
vote
1answer
51 views

Derive a ϴ(1) formula for a Recurrence relation

I'm given a piece wise function with sequence $a_0$ $a_1$ etc $$a_n = \begin{cases}8 & n=0\\-7 & n=1\\25 & n=2\\7a_{(n-2)}+6a_{n-3} & otherwise\end{cases}$$ I'm asked to derive a ...
1
vote
0answers
36 views

Recurrence relationships and a “weighted Pascal's triangle”

I was thinking about this problem a few days ago and in the process I came up with what I can best describe as a two-dimensional recurrence relationship. It seemed obvious to me that this was ...
1
vote
1answer
45 views

Solving a recurrence relation with no real roots?

$a_n - 2a_{n-1} -12a_{n-2} - 14a_{n-3} -5a_{n-4} = 0 $ I've tried a few method: setting the denominator to $1 -2x -12x^2 -14x^3 -5x^4$ and then finding the numerator by multiplying $(1 -2x -12x^2 ...