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

learn more… | top users | synonyms (2)

1
vote
1answer
33 views

Non-homogeneous Recurrence Relation with Fibonacci Sequence

I have this question in my assignment, I'm just not sure how to handle finding the closed form fully. I have most of it. Here's the question for context. Recall that the Fibonacci sequence is defined ...
0
votes
1answer
41 views

continuous evolution

I have a discrete evolution equation such that $$\rho(t+\tau) = M_0 \rho(t)M_0^\dagger+M_1 \rho(t)M_1^\dagger$$ $M_0\;\&\;M_1$ are two operators such that $tr(M_0^\dagger M_1)=0$ i.e. they are ...
1
vote
1answer
40 views

Finding the general term

I'm having some trouble with trying to find the general term of this sequence. It has a non-linear recurrence. I would really appreciate it if anyone could help me! $ a_{n}= \frac{c_{1}}{c_{2}-a_{n-1}...
1
vote
2answers
51 views

Find and solve simultaneous recurrence relations for determining n-digit ternary sequences whose sum of digits is a multiple of 3

I'm studying recurrence relations, and I ran into the following problem: Find and solve simultaneous recurrence relations for determining $n$-digit ternary sequences whose sum of digits is a multiple ...
4
votes
1answer
52 views

Assuming $0 \leq a_{n+1} \leq c_n a_n + b_n$ (+ other conditions), show $a_n \to 0$

In the paper "A primal-dual splitting method for convex optimization ..." (see here https://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/Condat-optim-JOTA-2013.pdf), Lemma 4.6 states the ...
25
votes
1answer
289 views

Is there an easy way to see that this simple recurrence is 9-periodic?

In a colloquium talk yesterday, Robert Bryant pointed out that for all initial values $a_0, a_1 \in \mathbb{R}$, the sequence generated by the recurrence relation $$ a_{n+1} = |a_n| - a_{n-1} $$ turns ...
0
votes
1answer
56 views

Recurrence proof problem

I need to show that $a_n= 2^n + a_{n-2}$ for $n$ is greater than or equal to $2$. Prior to that we are told that recursively define $a_0 = 1,\, a_1 = 3, a_2 = 5,\, $ and $ a_n = 3a_{n-2} + 2a_{n-3}$ ...
0
votes
1answer
45 views

Finding a recurrence that satisfies a sequence

Consider the sequence: $1,1,1,3,5,9,17,31,\ldots$ Find both a recurrence and a different sequence that satisfies this recurrence. Saw a decent pattern until the 31 appeared...Pretty stuck. ...
0
votes
1answer
37 views

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves. I'm learning about recurrence relations, and I'm struggling more with defining my ...
0
votes
1answer
21 views

How to find equation for this sequence of numbers?

I have a sequence of numbers 0, 1, 5, 19, .... This is the pseudocode to generate the sequence $c = 0$ for $i=0, 1, 2, ...:$ $ c = 3c + 2^i$ Does anyone know how I would write an equation $f(i)$...
1
vote
0answers
29 views

Hermite Polynomial

In a famous paper by Ait-Sahalia I have found this expression for the Hermite polynomial (pp 252, line -5): $$ H_{j+1}^{\prime}\left(z\right)=-(1+j)\,H_j(z)\quad (1) $$ where $H_j$ is the $j$-th ...
0
votes
3answers
55 views

explicit formula for $a_n$ and $b_n$ [duplicate]

Let $a_n$ and $b_n$ be natural sequence such that $$a_n+b_n\sqrt3=(1+\sqrt3)^n$$ How can I find explicit formula for $a_n$ and $b_n$
5
votes
2answers
147 views

Deducing the closed form for pentagonal numbers

Consider the sequence: $0,1,5,12,22,35,51,70,92,117,145,176,\ldots$ Find both a recurrence and a closed form for this sequence. I've done some research and found out that the majority of ...
1
vote
1answer
28 views

Find a functional equation for the generating function whose coefficients satisfy the relation

Find a functional equation for the generating function whose coefficients satisfy the relation: $\qquad{}$ $a_n = 3a_{n-1} -2a_{n-2}+2, a_0=a_1=1$ When I solve this, I get the function $g(x)-1-x=3xg(...
0
votes
1answer
22 views

Recurrence relations, trouble understanding the statement

I have been struggling with the English in some recurrence relations problems, since I am studying it on my own and I'm not in a combinatorial environment. Here is one in which I can't grasp what it ...
0
votes
1answer
25 views

Making a string with pieces of different length and fabric

You are making a string and have access to pieces of two different lengths, of length 1 inch and of length 2 inch. The 1 inch pieces come in 5 different fabrics and the 2 inch pieces come in 4 ...
0
votes
0answers
14 views

How to Compute Discrete Intrinsic Curvature

Given a function $f$, a region $S$ where this function is twice differentiable, and the property that all of its discrete difference series centered in $S$ converge within $S$ We have that $$ f''(x)...
1
vote
0answers
24 views

Cutting cheese into chunks [duplicate]

Into how many chunks can one cut a round piece of cheese with n straight cuts? Consider the $3D$ version My try: f(x) = number of pieces and $'x'$ as number of cuts. $f(1)=2$ $f(2)= 2 + f(1)$ ...
0
votes
1answer
31 views

Recurrence relation. Application to ternary sequences

The question is: How many ternary sequences have no double zero? For this I understand that our $n$-digit sequence either have $0,1,\dots,n$ zeroes, is this ok? If the answer of above is positive, ...
1
vote
0answers
23 views

Solve the recurrence $T(n) = T(\lfloor n/2 \rfloor)+ T(\lfloor n/3 \rfloor) + \lfloor n \log_2 n\rfloor$.

$T(0) = T(1) = T(2) = 1$. For $n \geq 3, T(n) = T(\lfloor n/2 \rfloor)+ T(\lfloor n/3 \rfloor) + \lfloor n \log_2 n\rfloor$. Express the above recursion in $O(n)$ notation. I know how to solve ...
0
votes
1answer
28 views

Solving recurrence relation $4a_n=\sum\limits_{k=1}^{n-1} a_k$

I'm trying to solve the recurrence equation $$\begin{cases}4a_n=\displaystyle\sum_{k=1}^{n-1}a_k\\[1ex]a_1=1\end{cases}$$ What I considered doing was subtracting $4a_{n-1}$ from $4a_n$: $$\begin{align*...
0
votes
0answers
18 views

How do you find the order of a recurrence relation?

I cannot find a straight forward answer in my book or online. A lot of the answers I found are very wordy and I have trouble understanding them. For example take this recurrence relation: Is the ...
0
votes
3answers
33 views

Solve the following recurrence relations

Solve the following recurrence relations: $\qquad$a) $a_n = a_{n-1} + 3(n-1), a_0 = 1$ $\qquad$b) $a_n = a_{n-1} + 3n^2, a_0 = 10$ I know that $a_n = a_{n-1} + f(n)$ = $a_0 + \sum_{i=0}^n f(i)$....
0
votes
2answers
37 views

A question related to linear recurrence.

I have seen examples such as Towers of Hanoi and Merge Sort, which I understand but when it comes to solving this kind of problems I just don't understand where to start. If given a solution to the ...
4
votes
2answers
129 views

Prove that this system of linear equations generates $\left| \left( \begin{matrix} 1/2 \\ n \end{matrix} \right) \right|$ as a solution?

This infinite system of linear equations: $$ \begin{array}( 2x_1=1 \\ 3x_1+4x_2=2 \\ 4x_1+5x_2+6x_3=3 \\ \cdots \end{array} $$ In other words, this is particular case of a system: $$ \begin{array}( ...
1
vote
1answer
22 views

Write a recurrence relation that models how your loan balance changes from month to month.

You have saved \$40,000 for a deposit on a home purchase. A cheerful Victorian home is on sale for \$370,000. You have qualified for a home loan mortgage at an annual interest rate of 3.6% compounded ...
0
votes
1answer
48 views

How does $a_{n+1}-2a_n=2a_{n-1}$?

I'm solving non-homogeneous linear recurrences for my combinatorics class and my teacher skipped a bunch of steps in his notes, so I am trying to make sense of a particular "step" he took. We were ...
1
vote
1answer
19 views

Prove that $\displaystyle\int_{x=-1}^{1}P_L(x)P_{L-1}\acute (x)\,\mathrm{d}x=\int_{x=-1}^{1}P_L\acute(x)P_{L+1} (x)\,\mathrm{d}x=0$

A question (Problem $7.4$) in my textbook (Mathematical Methods in the Physical Sciences - 3rd Edition by Mary L. Boas P578) asks me to Use $$\int_{x=-1}^{1}(P_L(x)\cdot\text{any polynomial of ...
0
votes
0answers
17 views

Asymptotic growth of $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$

Can you give a solution or a hint for finding asymptotic bound for following recurrence relation: $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$ I know from the source of the problem that it is $\...
2
votes
1answer
73 views

What is $\lim\limits_{n \to \infty} x_n$ where $x_1=2$ and $x_{n+1}=123+\sqrt{4+5 \sin(x_n) + 6\sqrt{x_n}}$?

$$x_{n+1}=123+\sqrt{4+5 \sin(x_n) + 6\sqrt{x_n}}, \quad x_1=2$$ At first glance, this sequence seems like it will diverge, since it seems like every term is growing by at least $123$. However, I ...
0
votes
0answers
11 views

Time taken to run a function R(n,a)

R(n, a){ if n = 1 return(a); if n > 1 return (R(n − 1) + R(n − 1) + 1); } Could you please explain me why the estimated time taken to run R(n, a) as a function of n is: (2^(n−1))*(a + 1) − 1 ? ...
4
votes
1answer
98 views

Find the number of points of distance n away from origin as function of n

I came across a seemingly simple problem the other day and I thought I'd share it with anyone interested. Say you have a point in 3 dimensions. The number of points that are of distance $0$ away is ...
0
votes
1answer
36 views

Integral of Legendre Polynomial

Determine the following integral $$\int_{-1}^{1}x^{2}P_{2n-1}\left(x\right) dx$$ Using the generating function and the fact that $\left(1-2rx+r^2\right)^{-1/2}=\sum^{\infty}_{n=0}P_{n}\left(x\right)...
1
vote
3answers
40 views

Prove that the $c_{n}$ in $\frac{1}{1-z-z^{2}}=\displaystyle\sum_{n=0}^{\infty}c_{n}z^{z}$ satisfy a Fibonacci-like recurrence relation

I need to prove that the coefficients $c_{n}$ of the expansion $\frac{1}{1-z-z^{2}}\sum_{n=0}^{\infty}c_{n}z^{n}$ satisfy the recurrence relation $c_{0}=c_{1}=1$, $c_{n}=c_{n-1}+c_{n-2}$, by ...
1
vote
1answer
22 views

Closed form solution for generating function

The recursion formula for some probability $P_n(s)$ is $$P_{n+1}(s) = qP_n(s+1) + pP_n(s-1).$$ Define the generating function $$G(z,n) = \sum_{s=-\infty}^{\infty} z^s P_n(s)$$ and prove the ...
0
votes
1answer
23 views

How to solve this linear functional homogenous recurrence relation?

I recently came across finding eigenvalues of a particular tridiagonal matrix and trying to reduce the problem, I came to a recurrence relation, which I don't know how to solve: $$a_i(\lambda)=(\...
2
votes
1answer
32 views

Closed Form Solution to Exponential Recursion

Is there a closed form solution to the function $f_n=2^{f_{n-1}}$ where $f_0=2$ ? For instance, the first few values of the function are 2, 4, 16, 65536.
0
votes
1answer
57 views

Recurrence relation for the number of ternary strings of length n that contain either two consecutive 0s or two consecutive 1s.

I'm having trouble with this one...I understand others have posted this it seems. However, I don't understand those answers/others some incorrect. I first tried thinking of the different ways this ...
0
votes
1answer
32 views

What does $[n=0]$ mean?

Namely, in the context of a recursively defined sequence: $a_n=a_{n-1}+b_{n-1}+a_{n-2}+[n=0]$ where b is an element of another sequence.
0
votes
0answers
67 views

Writing a closed polynomial from a difference table

Here is a difference table for a function $S(N)$. Your job is to fill in the table, and then write out the closed polynomial expression corresponding to $S(N)$. The third level difference row is ...
0
votes
0answers
13 views

Are these linear homogenous recurrence relations?

I'm having trouble understanding the formal definition because it is a bit wordy for me. However, the way I understood it is that to be homogenous, all the terms must have the same exponent. This is ...
0
votes
1answer
30 views

Did I solve this linear homogeneous recurrence relation correctly?

I'm not sure how to enter math on this site because I'm pretty new, but I typed my solution up on word. My solutions:
0
votes
1answer
40 views

How to solve this recurrence relation for a general $n$

We have a recurrence relation: $$a_n=1$$ $$a_{n-1}=x$$ $$a_{n-i}=xa_{n-i+1}-a_{n-i+2} $$ for $i=2,3,\ldots,n.$ How to find $a_0$ in terms of $x$? For a fixed $n$, I can solve it but it turns out ...
1
vote
2answers
30 views

How would I find the characteristic equation of this Recurrence Relation?

Find and solve a recurrence relation for the number of $n$-digit ternary sequences with no consecutive digits being equal. Since for ternary, meaning only $3$ possible entries for each space, e.g. $0$...
0
votes
0answers
25 views

Long-time behavior of a diffusion-like equation

I would like to known the long-time behavior of $\mathbf{u}_{t}(n)$ obeying the equation $ \mathbf{u}_{t+1}(n) = T_l\mathbf{u}_{t}(n-1) + T_0\mathbf{u}_{t}(n) + T_r\mathbf{u}_{t}(n+1) $ where $T_l = ...
0
votes
0answers
21 views

Asymptotic upper bound for recurrence relations

The question is to find asymptotic upper bound for recurrence: (1) $T(n)=(T(n/2))^2$ and (2) $T(n)=(T(\sqrt{n}))^2$ with $T(n) = \text{n for n} \leq 2$ I think I will be able to find the ...
0
votes
1answer
32 views

Asymptotic upper bound $T(n)=(T(n−1))^2$

The question is to find asymptotic upper bound for recurrence: $T(n)=(T(n−1))^2$ $T(n) = \text{n for n} \leq 2$ My attempt: I've tried to use substitution method and getting: $T(n) = ...
0
votes
1answer
22 views

Calculate $(\Delta^2+\Delta-2)^{-1} (n^3+1)$

Is this part correct: $$(\Delta^2+\Delta -2)^{-1} =\left( -2\left(I-\frac{\Delta^2+\Delta}{2}\right)\right)^{-1}=-\frac{1}{2} \left(I+\frac{\Delta^2+\Delta}{2}+\left(\frac{\Delta^2+\Delta}{2}\right)^...
0
votes
0answers
10 views

Struggling with Frobenius Solutions

$x^2y''+5xy'+(x+4)y=0$ where $y = \sum_0^\infty c_n x^{n+r}$ a - prove $x=0$ is a regular singular point (done) b - find the r's (done) c - find the solution (stuck) also, I know the r's are both ...
0
votes
1answer
26 views

Find a system of recurrence relations

Find a system of recurrence relations for the number of $n$-digit binary sequences with $k$ adjacent pairs of $1$s and no adjacent pairs of $0$s. Any help on how to go about doing this would be ...