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

learn more… | top users | synonyms (2)

2
votes
0answers
19 views

Help solving the recurrence $W(n)=W(n/5)+W(7n/10)+\Theta(n)$.

Let $W(n)=W(n/5)+W(7n/10)+\Theta(n)$ for $n>5$ and $W(n)=\Theta(1)$ for $n\leq 5$. I want to show that $W(n)\in \Theta(n)$. Attempt 1 I understand the technique used in this question that solves ...
2
votes
0answers
33 views

Solving the recurrence relation $a_k=3a_{k-1}+4a_{k-2}$ with $a_0=1$, $a_1=2$

Solve the recurrence relation $a_k=3a_{k-1}+4a_{k-2}$ with $a_0=1$, $a_1=2$ using characteristic equation. These are the steps I used. Is my work correct?
2
votes
0answers
42 views

Recurrence Relation - How to come up with a formula

Here is an example from "Discrete and combinatorial mathematics an-applied introduction" by Grimaldi. My problem is that I have a hard time following along with the arguments. Example: For $n\geq 1$ ...
2
votes
0answers
40 views

Find $\lim\limits_{n\to\infty}\frac{x_{n+1}}{x_n}! $ where $x_n=x_{n-1}+x_{n-2},x_1=1,x_2=2$

Find $\lim\limits_{n\to\infty}\frac{x_{n+1}}{x_n}! $ where $x_n=x_{n-1}+x_{n-2} ,(n>2),x_1=1,x_2=2$ $x_n=x_{n-1}+x_{n-2}$ $x_{n+1}=x_{n}+x_{n-1}$ From the first recurrence relation, ...
2
votes
0answers
52 views

A recursively defined sequence and a limit

Fix real numbers $ a_0 $, $ a_1 $ and define, $$ a_{n+1} = a_n + \Big(\frac{2}{n+1} \Big) a_{n-1} \space \space \forall \space n \ge 1 $$ Show that the sequence $ \Big\{ \dfrac{a_n}{n^2} ...
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?
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)$ ...
2
votes
0answers
84 views

Solving recursions by calculating determinant of an infinite matrix

In this reference (pg. 4) and few others a specific parameter in a recursion formula is solved by setting the determinant of an infinite matrix to $0$. In this precise case we have $c_{n-1} - D_n c_n ...
2
votes
0answers
19 views

Boundary difference equation, monotonicity of the solution properties.

let's say we have a function $f \in C^{\infty}[a,b]$ such that $f,f',f'' > 0 \forall x \in [a,b]$ What i would like to prove is that the solution of this boundary problem $$\left\{ ...
2
votes
0answers
50 views

Convergence of difference equation to differential equation

Starting with the difference equation: $$f(x(t+dt),t+dt)= (1-a)f(x(t),t) + a f(x(t+dt),t)$$ where $x(0)$ is given and positive, $a\in(0,1)$, $f(0,t)=0$, and $f$ is increasing in both arguments. ...
2
votes
0answers
36 views

Setting up a recurrence for Odd-Even Mergesort

Given the below algorithm How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort? What I've tried For ...
2
votes
0answers
44 views

Complicated recurrence relation

I would like to know if the following recurrence relation is solvable \begin{equation} (\alpha_{1}n^{2}+\beta_{1}n+\gamma_{1})\ c(n+1)+(\alpha_{0}n^{2}+\beta_{0}n+\gamma_{0})\ ...
2
votes
0answers
186 views

Recurrence relations book

I have never been good at solving recurrence relations. Part of the reason is that I have never found a book that is good at explaining the strategies for solving them; The books just give formulas ...
2
votes
0answers
35 views

asymptotics of Involutions recurrence relation

Consider the following recurrence relation where $t(n)$ is the number of involutions on $\{1,...,n\}$ \begin{equation} (n+1)t(n)+t(n+1)-t(n+2)=0 \end{equation} When $n \rightarrow \infty$, Wimp and ...
2
votes
0answers
117 views

Number of unordered factorizations into $k$ distinct parts

Let $H_d(n)$ denote the number of distinct ordered factorizations of $n$ and $H_d(n,k)$ the number of ordered factorizations of $n$ into $k$ distinct parts. We have the following recurrence: ...
2
votes
0answers
40 views

How many entries in the sequence $x_n$ given by recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ are known?

The sequence $x_n$ with the recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ , where $p_k$ denotes the $k-th$ prime, has the following values : ...
2
votes
0answers
23 views

Determining asymptotics of a function given a series of difference-like inequalities

I have a function $f: \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ and I know it satisfies the following properties. $f(x) \leq \frac{\log{\sqrt{2}}}{2x}$ and for all $A \geq 1$ and $B \geq ...
2
votes
0answers
38 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
2
votes
0answers
57 views

Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$ (y^2-1)^x $$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a ...
2
votes
0answers
42 views

Multivariable generating functions

Let's consider a 2-variable generating function for the Dyck triangle numbers. Reccurence, satisfying to the triangle conditions is $d_{n, k}=d_{n-1, k-1}+d_{n-1, k}+d_{n-1, k-1}$, $d_{0, 0}=1$, ...
2
votes
0answers
79 views

Derive a Recurrence

Could really use some help with this. For an integer $m \geq 1$ and $n \geq 1$, consider $m$ horizontal lines and $n$ non-horizontal lines, such that no two of the non-horizontal lines are parallel ...
2
votes
0answers
67 views

Generalizing the Fibonacci identity $F_{2n}=-F_{n-1}^2+F_{n+1}^2$

Using an integer relations algorithm, we get, $$F_{2n}=-F_{n-1}^2+F_{n+1}^2$$ $$6F_{4n}= -F_{n-2}^4-3F_{n-1}^4+3F_{n+1}^4+F_{n+2}^4$$ The pattern of the subscripts is clear. Expressing the ...
2
votes
0answers
199 views

How to solve this recurrence relation and solving the power series

Take the following recurrence relation into account: $$ a_{n+2} = \frac{1}{(n+1)(n+2)} \sum_{k=0}^n (s_k - (k+1)a_{k+1})(n-k+1)a_{n-k+1} $$ I know that: $$ s_{2m+1} = \frac{(-1)^m}{(2m+1)!} $$ and ...
2
votes
0answers
18 views

Need help in understanding the procedure of expanding recurrence formula

So here is the actual expansion: \begin{align} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &\vdots \\ &= T(0) + 1 + 2 + \ldots + (n-2) + (n-1) ...
2
votes
0answers
35 views

Why do I generally see real solutions to recurrence relations?

I haven't worked very much with recurrence relations, but for the ones I have worked with I always get real solutions, which is strange to me because looking briefly at the procedure for solving ...
2
votes
0answers
52 views

What techniques does Mathematica use to find solutions to these sequences?

This question is related to my previous question: Need help finding a closed form for complicated sum. An answer to that question led my to try and find the general term of the following recurrence: ...
2
votes
0answers
72 views

How to solve this tough recurrence relation?

For solving a related probability problem, I'm required to solve the following recurrence relation:- $q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times ...
2
votes
0answers
28 views

Deriving a recurrence equation and apply Master's Thrm to it

So for a function such as: function Hi(n) if n > 1 then for j ← 1 to n do print(”Hi”) Hi(n/2) Hi(n/2) Hi(n/2) It's very easy to eyeball this and get a ...
2
votes
0answers
51 views

Recurrence with Polynomial Coefficients of $n$

How would I solve or obtain a closed-form solution for a recurrence relation like $$a_n = f_1(n)a_{n-1} + f_2(n)a_{n-2} + ... + f_k(n)a_{n-k} + g(n)$$ where $f_1, f_2, ..., f_k, g$ are polynomials and ...
2
votes
0answers
42 views

Solve the recurrence $T(n)=aT(n-1)+bn$

I have to solve the following recurrence, given $T(1)=1$, $$T(n)=aT(n-1)+bn$$ I have done the following: $$T(n)=aT(n-1)+bn \\ =a^2T(n-2)+ab(n-1)+bn \\ =a^3T(n-3)+a^2b(n-2)+ab(n-1)+bn \\ = \dots \\ ...
2
votes
0answers
21 views

Finding Recurrence Relation in Closed Form or as Infinite Summation/Coproduct

My recurrence relation is: $$f(n)=(2n-3) f(n-1) -x^2 f(n-2)$$ Where $$f(-1)=1$$ $$f(0)=0$$ $$f(1)=-x^2$$ $$f(2)=f(1)$$ $$f(3)=-x^2 (3-x^2)$$ And it gets more complicated from there
2
votes
0answers
78 views

A similar, but hopefully easier problem than Gilbreath's conjecture

Gilbreath's conjecture says that for every positive integer $n$, if we write out the first $n$ primes $2,3,5,7,11,13,\ldots,p_n$ take the differences between consecutive terms ...
2
votes
0answers
89 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 ...
2
votes
0answers
48 views

How to solve a first order inhomogenous recurrence relation?

I have a recurrence relation for a fund that starts a 50 million, 6 % interest every year, and an outtake of 2 million/year. How to find out a solution for what funds exists after n years? ...
2
votes
0answers
39 views

Solution of partial difference equation

I want to find the explicit solution of the following difference equation $e_{i,j+1}=re_{i-1,j}+(1-2r)e_{i,j}+re_{i+1,j}+km_{i,j}$ where $r>0$, $k>0$ and $m_{i,j}$ are known and $e_{i,0}=0$. ...
2
votes
0answers
53 views

Recurrence Relation with $n^{\frac{1}{2^k}}$ Square Root

I tried to solve this recurrence relation, like the following: $$ \\ T(n) = \begin{cases} T(\sqrt[2]{n}) + c, & \text{if }n \geq 2 \\ a, & \text{otherwise} \end{cases} \\\\ T(n) = ...
2
votes
0answers
43 views

Infinitely many primes in second-order recurrence

I just wondered about the following question: Suppose that we are given a homogeneous second-order recurrence relation, $x_{n+2}+ax_{n+1}+bx_n=0$ for all $n\in\mathbb{N}$. Can we choose integers ...
2
votes
0answers
51 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
2
votes
0answers
118 views

How to solve a ceiling expression or recurrence equation?

I am trying to express the following in term of n, $$\underbrace{\hbox{$ \left \lceil \frac{3}{2}.\left \lceil { \frac{3}{2}.\left \lceil { \ldots \left \lceil \frac{3}{2}.\left \lceil { ...
2
votes
0answers
142 views

Special map $f(x_n)=x_{{n+1} [\mod 4]}$

As mentioned in the headline I am considering the map $f(x_n)=x_{{n+1} [\mod 4]}$. It looks a little bit similar to the dyadic (bernoulli) map but instead of $\mod 1$ we have $\mod 4$ which means that ...
2
votes
0answers
301 views

Induction proof of a recurrence relation

I have some trouble with an induction proof for the following problem. There is a vending machine that only takes coins of value 1 and 5 respectively. Let $S_n$ be the number of different ...
2
votes
0answers
52 views

Determinant of Stirling submatrix

Consider the table containing the Stirling numbers of the second kind $S\left( n,k\right) $. From this table construct a square matrix $M$ containing $N$ differents rows from the table ...
2
votes
0answers
150 views

How to solve this recurrence relation (related to discrete Fourier transform)?

I am having trouble with the following recurrence relation: $$c_{n+1} - c_{n-1} = 2\alpha \sin \frac{(2n-1)\pi}{N} c_n, \quad\forall n \in \mathbb{Z},$$ where $N$ is odd and the initial condition is ...
2
votes
0answers
104 views

Recurrence relation for polygamma reflection polynomials

In the reflection formula for the polygamma function $$ \psi^{(n)}(1-z) + (-1)^{n+1}\psi^{(n)}(z) % = (-1)^{n} \pi \frac{d^{n}}{d z^{n}} \cot (\pi z) $$ the right hand side is a polynomial ...
2
votes
0answers
185 views

Showing the relationship between Lucas and Fibonacci numbers with a recursive relationship

Given the equation $$L_{n+k}-(-1)^kL_{n-k}=5F_kF_n$$ Where $\{L\}$ is the set of Lucas numbers and $\{F\}$ is a Fibonacci sequence, $n$ and $k$ are both $>0$ and integers, how would one develop ...
2
votes
0answers
77 views

How prove this sequences have limts and find this value?

let $f:R\longrightarrow R$,and $f(x)=x-\dfrac{x^2}{2}$,and $$L_{1}(x)=f(x),L_{2}(x)=f(f(x)),L_{3}(x)=f(L_{2}(x)),\cdots,L_{n}(x)=f(L_{n-1}(x))$$ and let $$a_{n}=L_{n}\left(\dfrac{17}{n}\right)$$ ...
2
votes
0answers
61 views

Finding the best real value for $C$.

Consider the recurrence $f_{n+1}=f_n + \ln(f_n)$ with $f_0=2$. Also consider differential equations of type $g(0)=2$ and $\dfrac{d g}{d x}=\ln(g(x)- C \cdot \ln(g(x)))$. Lets call the solution ...
2
votes
0answers
93 views

Solving recurrence relation of algorithm complexity?

Supposing I write an algorithm that results into this kind of recurrence relation $$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
2
votes
0answers
163 views

Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...
2
votes
0answers
108 views

Is there a closed form for this recurrence?

Given $$ E_{n,k} = \begin{cases} 0 & \text{ if } n \leq k \\ n & \text{ if } k = 0 \\ \sum_{i=0}^{n-1} \dfrac{1}{n} \cdot E_{i,k-1} & \text{ otherwise } \end{cases} $$ I wonder is there ...