Questions regarding functions defined recursively, such as the Fibonacci sequence.
5
votes
1answer
189 views
A nicer recurrence for the Eulerian polynomials.
I was perusing the subject of Eulerian polynomials. I'm assuming the definition that the Eulerian polynomial is defined by $C_n(t)=\sum_{\pi\in S_n}t^{1+d(\pi)}$, where $d(\pi)$ is the number of ...
5
votes
1answer
30 views
Recurrence $u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$
I was going through some old puzzles and encountered one where there was a non-linear recurrence of form $$u_{n+1}u_{n-1}-u_n^2=Ar^{n-1}$$ with $u_0$ and $u_1$ given.
I know I can use a test form ...
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
1answer
216 views
Recurrence equation similar to a geometric progression
I have the following recurrence relation:
$$T(i) = \sqrt{T(i-1) \left(T(i+1) + k\right)},$$
with $k \geq 0$, a fixed constant.
I know that when $k=0$, we have:
$$T(i) = \sqrt{T(i-1) T(i+1)},$$
which ...
5
votes
0answers
368 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
5answers
182 views
What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?
What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$, $F(1)=b$ and $a,b>0$ ? It seems to be simple generalization of Fibonacci sequence but I can't find closed form for ...
4
votes
4answers
274 views
What's known about recurrences involving $(a_n)^2$?
I've run across the recurrence $a_{n+1} = (a_n)^2 + 1$ in the past. Unfortunately, the referrence escapes me. However, my impression was that recurrences involving the product of previous terms ...
4
votes
2answers
1k views
Why is solving non-linear recurrence relations “hopeless”?
I came across a non-linear recurrence relation I want to solve, and most of the places I look for help will say things like "it's hopeless to solve non-linear recurrence relations in general." Is ...
4
votes
4answers
168 views
Recurrence relation $C_n = n + 1 + \dfrac{2}{n}\sum\limits_{k=0}^{n-1}C_k$.
A Discrete Mathematics book from which I'm self-studying ("Discrete Mathematics and Its Applications", by Kenneth Rosen) asks me to do the following:
Given the following recurrence relation:
$$C_n = ...
4
votes
2answers
111 views
Does this problem have a name?
Recently our lecturer told us that it is an unsolved mathematical problem if the following while loop aka iteration ever terminates. Unfortunately I forgot to ask him what it is called. If someone ...
4
votes
2answers
979 views
Fibonacci, tribonacci and other similar sequences
I know the sequence called the Fibonacci sequence; it's defined like:
$\begin{align*}
F_0&=0\\
F_1&=1\\
F_2&=F_0+F_1\\
&\vdots\\
Fn&=F_{n-1} + F_{n-2}\end{align*}$
And we ...
4
votes
2answers
115 views
A Recurrence Relation Involving a Square Root
Consider the recurrence relation:
$a_{n+1} = \sqrt{a_n^2 -k},$
where $k>0$, $n\in\{0,1,n:a_n^2\geq k\}$, and $a_0>0$ is known.
Is it possible to obtain an expression for $a_n$ in terms of ...
4
votes
3answers
415 views
Solving a set of recurrence relations
I have the 7 following reccurence relations:
$A_n = B_{n-1} + C_{n-1}$
$B_n = A_n + C_{n-1}$
$C_n = B_n + C_{n-1}$
$D_n = E_{n-1} + G_{n-1}$
$E_n = D_n + F_{n-1}$
$F_n = G_n + C_n$
$G_n = E_n + ...
4
votes
4answers
204 views
The sum $\sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j$
A recent answer of mine to a question on Math Overflow includes the sum $$S(n,k,x) = \sum_{j=0}^n \binom{n}{j} \left\{ j \atop k \right\} x^j,$$ where $\left\{ j \atop k \right\}$ is a Stirling number ...
4
votes
2answers
251 views
What is the closed form of this recurrence relation
I have the following recurrence relation :
$$g(0) = c $$
$$g(i+1) = g(i) + (1-g(i))*g(i)^{2}$$
where 0 < c < 1. Is there any closed form for this relation? If not can you give me an upper ...
4
votes
2answers
220 views
How do I resolve a recurrence relation when the characteristic equation has fewer roots than terms?
I know how to solve "simple" recurrence relations. For instance, say you have:
$$c_0 = 20$$
$$c_1 = 30$$
$$c_n = 3 c_{n-1} - 2 c_{n-2}$$
We can write the characteristic equation as:
$$3x^{n-1} - ...
4
votes
1answer
245 views
$a_n=20a_{n-1}+12a_{n-2}$ recurrence relation question
Respected Sir,
Please solve the below problem. Please...
Consider the infinite $\displaystyle\mathbb{S}=\sum_{n=0}^{\infty}\frac{a_n}{10^{2n}}$, where the sequence $\{a_n\}$ is defined by ...
4
votes
3answers
1k views
Recurrence trouble: $T(n)=2T(n/2)+T(n/3)+\theta(n^2)$
I have to solve the following recurrence :$\displaystyle T(n)=2T(n/2)+T(n/3)+\theta(n^2)$
I have done the whole tree analyses and now I have to prove that $\displaystyle T(n) \leq ...
4
votes
3answers
103 views
Combinatorial Proof for a Recursive Sequence
For $n>3$ let $g_n = g_{n-1} + g_{n-3}$ where the recursion takes the value 1 for n = 0,1,2.
Prove that $g_{2n} = (g_n)^2 + 2g_{n-2}g_{n-1}$ combinatorially, $n > 1$.
For the time being I am ...
4
votes
3answers
69 views
Need help about solving a recurrence relation
I have a recurrence relation which is like the following:
$$
T(n) = 2T(n/2) + \log_2 n.
$$
I am using recursion tree method to solve this. And at the end, i came up with the following equation:
$$
...
4
votes
3answers
142 views
Maximum based recursive function definition
Does a function other than 0 that satisfies the following definition exist?
$$
f(x) = \max_{0<\xi<x}\left\{ \xi\;f(x-\xi) \right\}
$$
If so can it be expressed using elementary functions?
4
votes
4answers
157 views
What sort of math is this, and how would I solve it?
I'm taking a computer science class after several years away from school and so far I'm doing all right. However, we're covering some math and I'm drawing a blank on what to even call this concept, ...
4
votes
1answer
121 views
Finding the general formula $a_n$ for $a_n = \frac{1}{2a_{n-1}} + 2a_{n-2}$
How to calculate the general formula $a_n$ for the following sequence:
$$a_n = \frac{1}{2a_{n-1}} + 2a_{n-2}$$
where $a_1=\frac{1}{2}, a_2=\frac{1}{4}$
4
votes
2answers
244 views
Numerical method for finding the square-root.
I found a picture of Evan O'Dorney's winning project that gained him the first place in the Intel Science talent search. He proposed a numerical methods to find the square root, that gained him ...
4
votes
2answers
110 views
A mouse leaping along the square tile
A $n \times n$ square is made of square tiles of dimensions $1\times1$. A mouse can leap along the diagonal or along the side of square tiles. In how many ways can the mouse reach the right lower ...
4
votes
2answers
309 views
How to approach 2-Dimensional Recurrence Relations
How to solve the following 2-dimensional recurrence relation?
Let $n, n'$ be natural numbers $> 0.$ Let $r$ be a positive integer $\ge 0.$
$$ P(n+n',r) = \sum_{i=0}^{r} P(n, ...
4
votes
2answers
142 views
Solving a recurrence using substitutions
I have to solve this recurrence using substitutions:
$(n+1)(n-2)a_n=n(n^2-n-1)a_{n-1}-(n-1)^3a_{n-2}$ with $a_2=a_3=1$.
The only useful substitution that I see is $b_n=(n+1)a_n$, but I don't know ...
4
votes
2answers
550 views
How to solve this recurrence relation
What are some ways to solve this recurrence relation:
$a(n+1)=2 a(n) - a(n-1) -1, \text{ with }a(0)=0, a(10)=0?$
I tried to first convert this inhomogeneous equation into a homogeneous one following ...
4
votes
3answers
44 views
Solving a set of recurrence relation:
Solving a set of recurrence relation:
$a_n=3b_{n-1} , b_n=a_{n-1}-2b_{n-1}$
In addition, It's known that: $a_1=2, b_1=1$.
So i started by isolating $b_n \to b_n=3b_{n-2}-2b_{n-1}$
So i get the ...
4
votes
1answer
231 views
Summation Of Product Of Fibonacci Numbers
Im trying to find out a general term for the following summation of products of fibonacci numbers:--
$$\sum_{k=4}^{n+1} F_{k}F_{n+5-k}\; , n \geq 3$$
I tried using Binet's equation but I am ...
4
votes
4answers
477 views
Closed form solution of Fibonacci-like sequence
Could someone please tell me the closed form solution of the equation below.
$$F(n) = 2F(n-1) + 2F(n-2)$$
$$F(1) = 1$$
$$F(2) = 3$$
Is there any way it can be easily deduced if the closed form ...
4
votes
1answer
197 views
Towers of Hanoi - are there configurations of $n$ disks that are more than $2^n - 1$ moves apart?
This is an exercise from Chapter 1 of "Concrete Mathematics". It concerns the Towers of Hanoi.
Are there any starting and ending configurations of $n$ disks on three pegs that are more than $2^n - ...
4
votes
1answer
38 views
Can anyone help me finding recurrence relation in combinatoric?
Guys, I am having trouble finding recurrent relation.
A codeword is made up of the digits $0,1,2,3$ (order is important!). A codeword is defined as legitimate if and only if it has an even number of ...
4
votes
1answer
38 views
Find the common limit of $\frac{2}{1/a_n+1/b_n}$ and $\sqrt{a_n b_n}$
Let $a_0=1$ and $b_0=2$, then
\begin{align}
a_{n+1} &= \frac{2}{\frac{1}{a_n}+\frac{1}{b_n}}, \\
b_{n+1} &= \sqrt{a_n b_n}.
\end{align}
The sequences $(a_n)$ and $(b_n)$ converge to the same ...
4
votes
2answers
162 views
Enumerate certain special configurations - combinatorics.
Consider the vertices of a regular n-gon, numbered 1 through n. (Only the vertices, not the sides).
A "configuration" means some of these vertices are joined by edges.
A "good" configuration is one ...
4
votes
1answer
883 views
Find a big-O estimate for $f(n)=2f(\sqrt{n})+\log n$
While self-studying Discrete Mathematics, I found the following question in the book "Discrete Mathematics and Its Applications" from Rosen:
Suppose the function $f$ satisfies the recurrence ...
4
votes
2answers
131 views
Count the number of divisions of a set recursively
I'm trying to understand the reasoning behind the answer to the following question from an old exam.
Given a set $S_n = \{ 1, 2, 3,\dots n\}$ find how many divisions, $K_n$, there are of the set ...
4
votes
2answers
632 views
Second order homogeneous linear difference equation with variable coefficients
I was wondering if you would point me to a book where the theory of second order homogeneous linear difference equation with variable coefficients is discussed. I am having difficulties in getting ...
4
votes
1answer
95 views
Issue while applying Master Theorem
I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having ...
4
votes
1answer
183 views
Non-linear Recursion
I'm trying to prove (or disprove and improve if possible) that the sequence $a_{n+1}=\frac{a_n^2+1}{2}$, where $a_0$ is an odd number greater than 1 contains an infinite number of primes. However, I ...
4
votes
1answer
231 views
Solving (and proving) a combinatorial functional recursive equation
I have a sequence of functions $f_k(n)$ defined as follows:
$f_1(n)=n^{n-2}$
$f_k(n)=\sum_{i=1}^{n-1}f_{k-1}(i)\cdot(n-i)^{n-i-2}\cdot{n-k \choose n-i-1}$
My goal is to find and prove a closed-form ...
4
votes
1answer
144 views
Solving recurrence relation in combinatorics
I'm working my way through basic combinatorics questions with recurrence relation, and can't quite get my head about the right way of solving them.
For example, I have two following examples in my ...
4
votes
3answers
117 views
How do you solve this recurrence?
I have been trying to practice recurrence relations that can be solved by the master theorem and came across this.
Now the $4^{\textrm{th}}$ problem in that file is :
$$T(n) = 2^n ...
4
votes
1answer
92 views
finding hypergeometric solutions for a recurrence relation
I would like to find all the possible hypergeometric solutions for the recurrence relation defined as $$ (n+2)a_{n+2} - 2(4n+5)a_{n+1} + 8(2n+1)a_n = 0.$$
Is there any way to approach this problem in ...
4
votes
3answers
190 views
If $f(1) = 2$ and $f(n) = n \cdot f(n-1)$ then $f(n) \gt 2^n$ for all $n \gt 2$
I'm having a little difficulty in proving what are probably simple induction proofs. Here is the question.
Define function $f(n)$ as follows. $f(1) = 2$ and $f(n) = n\cdot f(n-1)$ when $n > 1$.
...
4
votes
1answer
55 views
Solving recurrence relation of the form $T(n)=T\left(\frac{nb}{a}\right)+T\left(\frac{(n-b)c}{a}\right)+n$
How do we solve a recurrence of the form:
$T(n)=T\biggl(\dfrac{nb}{a}\biggr)+T\biggl(\dfrac{(n-b)c}{a}\biggr)+n$ ?
I tried substituting $q=\dfrac{a}{b},\ r=\dfrac{a}{c}, \ s=\dfrac{bc}{a}$ to ...
4
votes
1answer
81 views
Recurrence relation for a function with an integral of the function?
Pardon my lack of tex skills, but what is the recommended procedure in the following scenario:
$$g(f) = 1+\int_0^{1-f} g\left(\dfrac{f}{1-x}\right)\,dx$$
I am not sure how to proceed in such a ...
4
votes
2answers
580 views
Recurrence $T(n)=T(n/2)+2^n$ and $T(n)=T(n/2+\sqrt n)+\sqrt{6044}$ , without (!) the master method
Given the Recurrences $$T(n)=T(n/2)+2^n$$ and
$$T(n)=T(n/2+\sqrt n)+\sqrt{6044}$$
Remark : $T(n)=1$ for $n\le 3$
I'm trying to find their upper bound & lower bound , which is probably $O(2^n)$ ...
4
votes
1answer
177 views
What types of functions do recurrence relations methods apply to?
I have been working with a function that I defined recursively as
$$a(n) = (1-a(n-1)^k)^k$$ where $a(0) = x$ and $k$ is an integer $>1$.
So really, $a(n)$ returns a function on $x$ and $k$.
I have ...
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}$.
