Questions regarding functions defined recursively, such as the Fibonacci sequence.
8
votes
0answers
117 views
A series: $1-\frac{1}{2}-\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\frac{1}{6}+\frac{1}{7}+\cdots$
Denote $$b_1=1,b_{n}=b_{n-1}-\dfrac{S(b_{n-1})}{n},(n>1 )\tag1$$
where $S(x)=1$ if $x>0,S(x)=-1$ if $x<0$, and $S(0)=0.$
So ...
6
votes
0answers
113 views
How does one prove that $\zeta(3)$ is irrational?
How does one prove that $\zeta(3)$ is irrational ?
I would like to know how Apery did it. In particular how a recursion gives rise to irrationality !?
5
votes
0answers
58 views
Properties of a continued fraction convolution operation
Usually the partial numerators of a continued fraction are all 1s.
Has anyone considered the operation where you convolve 1 continued fraction with another, in other words, make a new continued ...
5
votes
0answers
367 views
The Average Running Time Of Euclid Algorithm?
What is the average running time of Euclid Algorithm with respect to all possible input pairs $(m,n)$ such that $\gcd(m,n) = d$?
It seems very hard to deduce from the recurrence
$T(m,n) = T(n, m ...
4
votes
0answers
88 views
What is a good asymptotic for $f_n = f_{n-1}+\ln(f_{n-1})$?
Let $f_0=2$ and $f_n=f_{n-1}+\ln(f_{n-1})$. What is a good asymptotic to the sequence $f_n$? With good I mean much better than $f_n \sim \dfrac{3n \ln(2)\ln(n)}{2}$.
4
votes
0answers
140 views
Recurrence relation for the integral, $ I_n=\int\frac{dx}{(1+x^2)^n} $
Express recurrence relation of the integral
$$
I_n=\int\frac{dx}{(1+x^2)^n}
$$
[My Answer]
$$
I_n = \int\frac{1+x^2}{(1+x^2)^n}dx-\int\frac{x^2}{(1+x^2)^n}dx
$$
$$
I_n=I_{n-1}-\int ...
4
votes
0answers
163 views
A functional recursion problem..do you have any idea?
I have a problem which is related to algebra and polynomials. I would be very grateful if any of you could give a hand to solve it. Here is the problem: Consider the function $f_0(x) =x(1-x)$ and for ...
4
votes
0answers
141 views
Asymptotic behaviour of a two-dimensional recurrence relation
This problem comes out of a research in models of firm growth.
The model is simple: A firm has two parameters which are its size (number of employees) and job vacancies. A firm of size $n$ will ...
3
votes
0answers
27 views
Recurrence Relation
How do I solve:
$k(k+1)a_{k}=2(\lambda k-1)a_{k-1}+(a-\lambda^2)a_{k-2}$
where $\lambda$ and $a$ are constants, and similar other recurrence relations?
3
votes
0answers
37 views
Order of Recursion?
Define an extended algebraic function f(a) as a function on a that utilizes any combination of recursive extensions and inversions of sequentiation. Example:
a + 1 = sequentiation. a + a = addition ...
3
votes
0answers
80 views
How to resolve this equation for f(n) without using f(n-1)
I have an equation related to some work I'm doing on Poisson distribution where I'm calculating a sequence of 100 values between a minimum and maximum value which is set by another formula. ...
3
votes
0answers
56 views
Lower Bound on fibonacci-like reccurence relation
Given the following recurrence:
$T(n) := T(n-k) + T(n-1),\ n,k \in N$
$T(l) := 1,\ l \in \{0,...,k-1\}$
I need to find a lower bound for $T(n)$. (For $k = 2$, the recurrence is equal to the ...
3
votes
0answers
39 views
An interesting partial recurrence equation
What is the closed form solution to the following partial recurrence relation?
$$f(k,n) = \sum\limits_{t=0}^{m}f(k-t, n-1),$$
where $ m \geq 0$ is some fixed parameter.
The boundary values are ...
3
votes
0answers
56 views
Properties preserved under the “reversal” of a recurrence equation
Consider the recurrence equation
$u_n = f(u_{n-1},\ldots, u_{n-k})\;,$
defined for $n=0,1,2\ldots$.
If this is a linear recurrence and the coefficient function on $u_{n-k}$ is nonzero in ...
3
votes
0answers
148 views
Is this a recurrence for the Mertens function plus 2?
If we define a symmetric array:
$$T(1,1)=3,\; T(1,2)=2,\; T(2,1)=2$$
$$T(1,k)=\frac{-T(n,k-1)-\sum\limits_{i=2}^{k-1}T(i,k)}{k+1}+T(n,k-1)$$
$$ ...
2
votes
0answers
48 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
83 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 ...
2
votes
0answers
45 views
How much information do I gain from each modular inequality?
Problem details:
Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants.
Furthermore let $f(x) = a x + b \pmod{p}$
and let the value $r_k$ be defined by the first-order recurrence ...
2
votes
0answers
47 views
how to compute $\lim_{n\to\infty}\ln(f(n))/\ln(n)$ for this given $f(n)$?
Let $c=f(0)$ be a real number and $n,m$ positive integers. Let $P_k(n)$ be integer polynomials of $n$.
Let $f(n)$ be defined by the recursion $\left[\sum_{k=0}^{m} P_k(n)f(n+k)\right]+P_{-1}(n)=0$.
...
2
votes
0answers
203 views
Probability of tossing a biased coin without having k heads consecutively in a row
I got asked by a friend this question; I have a coin, the probability of receiving a head by tossing is $p$ and tail $1-p$. I have to toss it $n$ times without getting $k$ heads in a row. What is the ...
2
votes
0answers
148 views
How to solve non-linear recurrence relation in general?
For linear recurrence, we can use generating function. So is there a general technique to solve non-linear recurrence or it depends on a specific sequence? For example,
$$a_{n+1} = \dfrac{a_n(a_n - ...
2
votes
0answers
94 views
Linear multivariate recurrences with constant coefficients
In the theory of univariate linear recurrences with constant coefficients, there is a general method of solving initial value problems based on characteristic polynomials. I would like to ask, if any ...
2
votes
0answers
186 views
Asymptotics for the expected length of the longest streak of heads.
As Introduction to Algorithms (CLRS) describes, the problem is
Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see?
The book claims ...
2
votes
0answers
69 views
Perrin numbers in terms of the generalized hypergeometric function?
Given the roots of $x^3=x^2+1$, we have sequence A001609,
$M(n) = x_1^n+x_2^n+x_3^n = \,_3F_2(\frac{-n}{3}, \frac{1-n}{3}, \frac{2-n}{3};\; \frac{1-n}{2}, \frac{2-n}{2};\; -\frac{3^3}{2^2}) = 1, 1, ...
2
votes
0answers
125 views
Solving two-parameter linear recurrence with different initial values
I'm looking for a method to solve the well-known recurrence ralation with different initial values. The one-parameter linear recurrence is easier. Let's take a peek:
$a_0 = \alpha$; $a_1 = \beta$; ...
2
votes
0answers
97 views
How to solve the recursive relation in Kalman filter?
I was wondering how to solve the Kalman filter's recursive
equation (also see the appendix at the end of this post) for the estimated state $\hat{\textbf{x}}_{n|n}$ at
time $n$, over discrete times ...
2
votes
0answers
214 views
Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$
On pages 95 and 96 of the third edition of the CLRS book, we find
the following, which applies here since $a=b$ is all
it takes to block the application of the Master Theorem: "Although
$n\lg n$ is ...
2
votes
0answers
281 views
recurrence relation with non constant coefficients
I'm trying to solve a second order differential equation and I got a recurrence. Can someone help to solve $$n(n-1+q)a_{n}-a_{n-3}+e\cdot a_{n-2}=0$$ where $q$, $e$, and $a_{0}$ are some real numbers ...
2
votes
0answers
41 views
On bounding the average cost of top-down merge sort
Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that
$$
A_0 = A_1 = 0;\quad A_n = ...
2
votes
0answers
162 views
Bell-like recurrence
Let
$$A(n)=\sum_{k=0}^{n-1}\binom{n}{k}A(k)+n!,\quad A(0)=1$$
$$B(n)=\sum_{k=0}^{n-1}\binom{n}{k}B(k)-n!-n!\sum_{k=1}^{n}\frac{1}{k!},\quad B(0)=-1.$$
I'm interested in computing $S(n)=A(n)+B(n)$ ...
1
vote
0answers
39 views
Bounding a sequence defined recursively
Let $\{x_n\}$ be a sequence of positive numbers and $\alpha \in (0,1)$. Let $y_0 := x_n$ and
$$
y_k := (\alpha \,y_{k-1} + 1-\alpha) x_{n-k}
$$
for $k=1,2,\dots,n-1$.
Is it possible to give a sharp ...
1
vote
0answers
30 views
Help with Computational complexity of recurrence relation, Big Omega, Big O and Big Theta problem.
The problem that I am struggling with is the recurrance relation
T(n) = floor(T(n/2)) + ceiling(T(n/2)) + ceiling(n/2)
I am supposed to answer true/false to each of the following (along with ...
1
vote
0answers
25 views
genealogy pedigree chart
What is the simple expansion of a (simple) genealogy pedigree chart, where each person (only) has 2 parents? What is that called? Is it an arithmetic progression, or a geometric progression? You start ...
1
vote
0answers
113 views
1
vote
0answers
34 views
Recurrence with cases
$\def\left{\operatorname{left}}\def\right{\operatorname{right}}$I have the following recurrence with cases:
$$
p(l, r, s) = 0.5 \cdot \left(l, r, s)
+ 0.5 \cdot \right(l, r, s)
$$
...
1
vote
0answers
124 views
Two variable recurrence relations
I'm interested in solving the following type of problem...
Starting with a recurrence relation in multiple variables, for example:
$$ v_{i-1,j} + v_{i,j+1} + v_{i+1,j} + v_{i,j-1} = 4v_{i,j}$$
with ...
1
vote
0answers
77 views
Cycle of remainders
Let $N, K, W$ be natural numbers
If I start from $R_0$, say any integer $r_0, 0 \lt r_0 \lt N$
and proceed with:
$$R_j = ( R_{j-1} + K ) \mod W,\quad j=1,2, \dots$$
(that is the remainder of the ...
1
vote
0answers
67 views
Let $f(x+1) = P(f(x),x)$ where P is a polynomial. Express $f(x)$ as an integral.
Let $x$ be a real number and $f(x)$ a real analytic function such that $f(x+1) = P(f(x),x)$ where $P$ is a given real polynomial.
Express $f(x)$ as an integral from $0$ to $\infty$.
As an example we ...
1
vote
0answers
102 views
two dimensional recurrence
We have the following recurrence relation for $a_{n,m}$
$a_{n,m}=4a_{n+1,m-1}+\sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-1-i,m-j}$
with the boundary condition $a_{n,0}=c_n$ for $n\ge0$ where $c_n$ ...
1
vote
0answers
83 views
Evaluating iterated sine function
Let $f(x,1)=\sin(x)$ and $f(x,i)=f(\sin(x),i-1)$ ($f$ is the iterated sine function). For arbitrary $N$,$x_0$, how quickly can $f(x_0,N)$ be computed?
Answer to this question discusses ...
1
vote
0answers
122 views
Closed form expression for a recurrence relation.
Hello, any ideas for computing closed form for a recurrence relation?
In an attempt to compute what the $i$-th post order element would be in terms of its in order position in a complete binary tree, ...
1
vote
0answers
51 views
Bivariate recurrence relation
Consider the following recurrence relation:
$$A(h,0)=1\\
A(h,h)=c^h\\
A(h,r)=A(h-1,r)+(c-1)\cdot A(h-1,r-1).$$
Obviously, this is just a generalization of A008949, where $c=2$. Since I'm pretty sure ...
1
vote
0answers
119 views
Recurrence relation for the digits of the integer square root in binary
I was investigating a question on the Electrical Engineering Stack Exchange site, available here: ...
1
vote
0answers
61 views
Construction of polynomials with non-commutative elements.
I have a simple set of polynomials which I know how to construct for each integer $n$, but I havn't been able to write them down in terms of concrete sums and products.
For $n\in\mathbb N_+$, we have ...
1
vote
0answers
84 views
Achieving the “mirror” of exponential decay
I'm working on a product that has a visual transition. I've found that applying a simple filter that results in an exponential decay (starting fast, then tapering off) is pleasing in one direction. ...
1
vote
0answers
116 views
recurrence relation of general difference polynomials
I have a sequence of difference polynomials (which I obtained by the method of finite differences) and I would like to find out if there is a recurrence relation between them.
The generating function ...
1
vote
0answers
103 views
Find $G(n)$ with $n \geq 1$
Let $G(1) = 0, \ G(2) = 1$, $G(2n+1) = 2 + G(n) + G(n+1)$ and $G(2n) = 1 + G(n), \ \ n \geq 1$
Find $G(n) $
P.S: This is little problem in my problem. I tried to solve by using generating function, ...
1
vote
0answers
76 views
How to find the recurrence polynomial?
Problem:
If $f$ is a polynomial with unknown roots $x_1,-x_1,x_2,-x_2\ldots,x_b,-x_b \quad (b \in \mathbb{N})$ and can be expressed as (known expansion):
$$f(x)=\sum_{a=0}^{2b}f_ax^a\quad(b \in ...
1
vote
0answers
67 views
Recurrence $A_{n+1}=A_{n}+\mathbf{E}G_n$
This looks like a straightforward recurrence, but I have an impression I made a mistake somewhere. In this equation $G_n$ is a random variable
$
G_n=\left\{
\begin{array}{c c}
0 & 1-p_n \\
...
1
vote
0answers
160 views
Solve recurrence relation $a(n)=2\cdot a(n-1)+5\cdot a(n-2)+6\cdot a(n-3)$ and the associated cubic
I am trying to solve following :
$$a(n)=2\cdot a(n-1)+5\cdot a(n-2)+6\cdot a(n-3)$$
with the initial conditions given by $a(0)=3,a(1)=2,a(2)=14$.
So first of all, I want to mark that there exists ...
