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

learn more… | top users | synonyms (2)

2
votes
0answers
32 views

Calculate n-th term of a recursive formula

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $10^9 ...
2
votes
0answers
50 views

Finding the Generating Function given a Complex Recurrence

I have the following recurrence relation: $G_0=0, G_1=1,$ $$\left(G+\frac{2}{3}\right)^n+\left(G+\frac{1+w_3}{3}\right)^n+\left(G+\frac{1+w_3^2}{3}\right)^n=0, n>1$$ where $w_3$ is the primitive ...
2
votes
0answers
16 views

Is there a formula for nested quadratic functions?

Notation: $f^{(1)} (x) = f(x) \\ f^{(n)} (x) = f\left( f^{(n-1)}(x) \right)$ I'm looking for an explicit function, $f^{(n)} (x)$, where $f(x)$ is an arbitrary degree $2$ polynomial, or a nested ...
2
votes
0answers
22 views

Solving recurrence relation, no clue how to approach

I'm trying to solve the following recurrence relation $$T(n)\le T\left(\frac{3n}{4}\right)+T\left(\frac{n}{\log n}\right)+C\cdot{n}\log\log n$$ The answer should be $T(n)=\Theta(n \log\log n)$ ...
2
votes
0answers
29 views

Need reference for fact about roots of characteristic polynomials of recurrences

Many famous sequences $\{a_n\}$ satisfy recurrence relations. For example, the Fibonacci numbers $\{0,1,1,2,3,5,\ldots\}$ and Lucas numbers $\{2,1,3,4,7,11,\ldots\}$ both satisfy $$ a_n = a_{n-1} + ...
2
votes
0answers
44 views

Fundamental theorem of arithmetic, prove that these matrices are the same apart from the main diagonal.

I know and I can prove that the fundamental theorem of arithmetic is encoded uniquely by this recurrence written in Mathematica 8: ...
2
votes
0answers
36 views

Recurrence Relations

...
2
votes
0answers
14 views

Recurrence $x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$ solution

Let $x_k$ be the solution of the recurrence equation $$x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$$ where $(r_k)$ is a general sequence. I'm trying to find a explicit solution for $(x_k)$ ...
2
votes
0answers
65 views

Closed form of $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $

Given the sequence $a_1 = 1$ and $a_2 = 1 $ with: $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $ Does there exist a closed form computing $a_n$ ? At the moment I have a problem getting a grip on the ...
2
votes
0answers
23 views

Is $\sum \frac{n+1}{b_{n+1}}$ irrational, when $b_1=2$ and $b_{k+1}=2^kb_k(b_k-1)+1$, $k\geq 1$?

Let the sequences of positive integers $$a_n=n$$ when $n\geq 1$, and $$b_{n+1}=2^nb_n(b_n-1)+1$$ for $n\geq 1$ taking $b_1=2$. I've computed with previous sequences to assert that satisfy the ...
2
votes
0answers
47 views

Asymptotics of recursion

suppose we have the following two sequences $$\alpha_k = (k-1)\left(1-\frac {1}{1+(k+1)l}\right) \quad , k \geq 2$$ $$\beta_k = (k-1)\left(1+\frac {1}{1+(k-1)l}\right) \quad , k \geq 2$$ where ...
2
votes
0answers
27 views

Solving recursions with max

The question is general, but I'll first give a simple example. Suppose you have a candy machine with $N$ candies. The machine is weird, when you give it a quarter it gives you $1$ to $N$ candies (all ...
2
votes
0answers
27 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
41 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
49 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
57 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
54 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
95 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
52 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
71 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
47 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
275 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
42 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
133 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
42 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
45 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
62 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
43 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
69 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
211 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
36 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
73 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
30 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
61 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
47 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
79 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
90 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
49 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
46 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
52 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
122 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 { ...