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

learn more… | top users | synonyms (2)

9
votes
1answer
330 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 !?
-1
votes
3answers
25 views

Solving recurrence relation using Master Method

How to solve following recurrence relation using Master's Theorem?? $T(n) = T(n-10) + n.$ And if there is any other way despite Master's method to do this simpler way, what is it?
1
vote
1answer
38 views

Generating Series and Recurrence Relation and Closed Form

We have the following recurrence relation: $b_n=2b_{n-1}+b_{n-2}$ and initial conditions $b_0=0, b_1=2$ I use the generating series method to solve as following: Let ...
0
votes
3answers
55 views

recurrence relations and generating functions - I need a hint

I need to find "closed form" to the recurrence relation given by: $a_{n+1} = \sum_{k=0} ^ {n} k a_{n-k}$ and $a_0 = 1$. I have tried using generating functions but it is no good. Any help would be ...
2
votes
1answer
29 views

Limit of a recurrence

I was given the following exercise as homework: find the limit of $b_{n+1} = \sqrt{2 + b_n}$, $b_1 = \sqrt{2}$, with a hint that $b_n < 2 \forall n \in \mathbb{N}$. I have proven that $b_n$ is ...
1
vote
0answers
15 views

asymptotic of an interesting recurrence realtion (more general case)

A link to the original question for reference:Click here I tried to study a more general situation: Let $y_{d,d}=1$ and $$ ...
1
vote
1answer
60 views

Asymptotic of an interesting recurrence relation

I want to study the asymptotic behavior of the following recurrence relation: $y_1=1$; $y_{n+1}=y_n+\left(1+\frac{y_n}{n}\right)^{-n}$ for $n\ge 1$. I made an initial attempt and guessed that ...
2
votes
0answers
17 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
20 views

Recurrence relation for ternary sequence

Find the recurrence relation for number of ternary strings that do not contain two consecutive 0's or 1's. Strings that contains only 0s, 1s and 2s are called ternary strings. Answer is $a_n =2 ...
1
vote
3answers
941 views

Recurrence relations - binary substrings

Let $S_n$ be the number of binary strings of length = $n$ which do not contain the sub-string $010$. Find a recurrence relation for $S_n$. edit: I tried for $n=4$. There are two positions in ...
1
vote
2answers
18 views

recurrence relation for strictly increasing sequence

Find recurrence relation for number of strictly increasing sequences of positive integers such that first term is 1 and last term is n, where n is a positive integer. That is sequence a.1, a.2, a.3, ...
1
vote
0answers
19 views

FFT multiplication

I'm currently implementing a specific polynomial multiplication algorithm for a project. The current goal is to implement chapter 2 of Daniel Bernstein's paper ...
1
vote
1answer
70 views

Solving a recurrence involving binomials.

Does anybody know how to solve the following recurrence? Maybe with generating functions? Any hint? $t(n) = 1 + \frac{1}{2^{n-1}} \sum_{i=0}^{n-1} {n \choose i} t(i)$
1
vote
4answers
38 views

Solving this Recurrence Relation in terms of previous values.

What will be the value of $X(n)$ and $Y(n)$ in terms of given $n,X(0),Y(0)$. $$ X(n) = X(n-1) + Y(n-1) \\ Y(n) = 2X(n-1) + Y(n-1) $$
1
vote
0answers
44 views

Setting up and solving a recurrence relation

Assume we have two lists, $A$ and $B$; both are sorted lists each with $n$ elements (assume $n$ is a power of 2). We want to recursively merge the odd-indexed elements from each list: merge $a_1, ...
7
votes
1answer
590 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 ...
3
votes
3answers
54 views

Set up difference equation for the following recurrence.

I have the following recurrence: $t=0: 0$ $t=1: 0$ $t=2: 1$ $t=3: \beta+\alpha$ $t=4: (\beta+\alpha)\alpha+\beta^2$ $t=5: ((\beta+\alpha)\alpha+\beta^2)\alpha+\beta^3$ ... I was hoping to do ...
3
votes
4answers
61 views

Can this recurrence relation be solved with generating functions?

I have this recurrence relation, $$a_{n+1}=\frac{n+2}{n}a_n$$ with $a_1=1$. I've already solved this using a substitution approach by letting $a_n=\dfrac{(n+1)!}{(n-1)!}b_n$. This means ...
0
votes
1answer
13 views

Guessing particular solution for a recurrence relation with multiple quasi-polynomials on the right side

I'm trying to solve this recurrence: $$a_{n+2}+2a_{n+1}-3a_{n}=n+n(-3)^{n-1},\ a_0=0, a_1=1$$ However, the algorithm in my textbook doesn't seem to mention this case with multiple quasi-polynomials ...
4
votes
2answers
127 views

A summation involving multinomial coefficient

We need to find out $$\sum {\binom{N}{a_1,a_2,a_3...a_B} a_1^{\alpha}a_2^{\alpha}...a_C^{\alpha} }$$ $$a_1+a_2...a_B=N, \alpha>0 ,0\lt C \le B$$ All are nonnegative integers. We need to sum ...
0
votes
2answers
35 views

are there any functions that fit this recurrence relation

Would anyone know if there any functions that fit this recurrence relation: $F_n = \frac{1}{n+3/2} \left ( F_{n+2} - c F_{n+1} \right )$ where $c$ is a constant parameter. or, more general: $F_n ...
3
votes
5answers
187 views

Amateur Math and a Linear Recurrence Relation

I haven't received a formal education on this topic but a little googling told me this is what I am trying to find. I would like to put $$ a_n = 6 a_{n-1} - a_{n-2} $$ $$ a_1 =1, a_2 = 6 $$ into its ...
4
votes
3answers
50 views

Let $g_{n}$ be the no. of derangements with $n$ elements and $f_{n}$ the no. of permutations with one fixed point. Show that $|g_{n}-f_{n}|=1$

This is a problem from Loren Larson's "Problem solving through problems", 2.5.13, page 78. Let $S_{n}=${$1,2,...,n$}. A derangement of $S_{n}$ is a permutation with no fixed points. Let $g_{n}$ be ...
0
votes
1answer
23 views

solving non-homogeneous recurrence relation

solve the equation $a_n − 4a_{n−2} = −3n + 8$ for initial values $a_0=2, a_1=1$ I'm stuck on finding the particular solution for $a_n$. I tried using the form $a_n = C_1n + C_2$ but that gets me ...
4
votes
3answers
63 views

Limit of $f_{n+1} = \sqrt{12 + f_n}$ with proof by contradiction

Consider the following recursive sequence: $$ \begin{cases} f_{0}=\sqrt{12}\\ f_{n+1}=\sqrt{12 + f_{n}} \end{cases} $$ for $n \geq 0$. How can I prove that this sequence is bounded above by $4$ and ...
2
votes
1answer
30 views

Optimizing an asymptotic recurrence relation with two recursive terms

I have a recurrence relation that looks like this: $T(n) = 2 T(c n) + T((1-c)n) + O(1)$ The base case is just $T(b) = 1$ when $b \leq 1$. I'm trying to figure out the best value of $c \in (0, 1)$ ...
0
votes
3answers
103 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
1
vote
3answers
33 views

solve non homogeneous recurrence relation with only '1' as root of its equation [closed]

I'm stuck in this relation: $f(n) = f(n-1) + 3n - 1$ I've tried to search everywhere if I could find this kind of example where there is only root and that is '1' but all in vain. And all the ...
3
votes
1answer
47 views

Product of a Finite Number of Matrices with a Cosine Entry

Does any one know how to prove the following identity? $$ \mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix} 2\cos\frac{2j\pi}{n} & a \\ b & 0 \end{pmatrix}\right)=2 $$ when $n$ is ...
1
vote
0answers
28 views

Recursive function with two variables

How should I find an explicit solution for the following function: $$f(n,m)=a \, f(n-1,m+1)+b \, f(n-1,m)+c \, f(n-1,m-1)$$ where $f(1,0)=a+b$ and $f(1,1)=c$ for $n\geq 1$, $m\geq 0$. Also ...
0
votes
1answer
34 views

How can we solve a multi-variable recurrence relation in closed form, when the number of terms is also variable?

Consider the formula $f(x, y) = f(x, y-1) + 2 \sum\limits_{i=1}^{x-1} f(i, y-1) $ The factor '2' makes this not expressible cleanly as $f(x, y) = f(x, y-1) + f(x-1, y)$, which is solved here using ...
2
votes
1answer
77 views

Relations between the solutions of a non homogenous second order difference equation and their derivative?

Here's an excerpt of a lecture note I am reading (I've highlighted the beginning of the part that I don't understand): I don't understand how derivative comes into the picture. Here's some context ...
0
votes
0answers
8 views

Solving systems of reccurence equations to get number of recursions to reach a stationarity point?

I'm tring to solve a system of recurrence equations to then formalize a formula depending on the number of recursions to calculate this number of recursions to reach the stationarity of the system ...
0
votes
1answer
24 views

Recurrence relation to find time-complexity

I have the following simple C-program: int factorial(int n) { if(n==0) return 1; else return n*factorial(n-1); } Now, if I take the ...
8
votes
4answers
582 views

Closed form for a non-linear recurrence

Does equation $a_n=\sqrt{a_{n-1}+6}$ with $a_1=6$ have a closed form? I've found no linearization method. Any suggestion or hint will be highly appreciated.
1
vote
2answers
54 views

How to analyze convergence of non-linear difference equation (recurrrence relations)

I've a couple of functions, such as: $Y(t+1)=2-\ln(Y(t))$ $Y(t+1)=(Y(t))^{-2}$ $Y(t+2)=e^{-Y(t)}$ and I need to analyze stability and convergence. No problem with stability, but I can't figure out ...
1
vote
1answer
25 views

Caculation of involving Hermite polynomial

I have a trouble with this problem involving Hermite polynomial(probability version!). The problem is $$ \frac {(-1)^{r-1}H_{2r-1}(x)}{2^{r-1}(r-1)!x}=\sum_{s=0}^{r-1}\frac{(-1)^s}{2^ss!}H_{2s}(x) $$ ...
2
votes
3answers
37 views

Prove that $(2n+1)k_{n+1}=(2n+1)k_{n}+\cos^{2n+1} (x)$

Given that $$k_n=\int \frac{\cos^{2n} (x)}{\sin (x)} dx$$ Prove that $$(2n+1)k_{n+1}=(2n+1)k_{n}+\cos^{2n+1} (x)$$ I have tried to prove this is true by differentiating both sides with product rule: ...
0
votes
1answer
129 views

Fractional-Recursive Sequence

Here from the fraction set we have a really hard question to be answered...suppose that a sequence is defined as $a_{n} = a_{n-1} - \dfrac 1{a_{n-1}}$, where $a_0$ is given. ...you already know what ...
1
vote
1answer
29 views

Finding the closed form of recurrent sequences

What are the famous (general) methods to find the closed form of a given recurrent sequence? The only method I know of is the "generating function" method. However it only works in very special ...
0
votes
2answers
25 views

Proving guess wrong used for substitution method

Following is my recurrence relation : $T(n) = 2T(n−1) + c_1$. Complexity: $O(2^N)$. I want to prove it by substitution method/ mathematical induction (You can get insight of it from : ...
17
votes
4answers
4k views

Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...
9
votes
4answers
126 views

Prove the series has positive integer coefficients

How can I show that the Maclaurin series for $$ \mu(x) = (x^4+12x^3+14x^2-12x+1)^{-1/4} \\ = 1+3\,x+19\,{x}^{2}+147\,{x}^{3}+1251\,{x}^{4}+11193\,{x}^{5}+103279\, ...
0
votes
2answers
103 views

Sum of roots of binary search trees of height $\le H$ with $N$ nodes

Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees. For example, for $N$ = 3, $H$ = 3: ...
0
votes
0answers
30 views

Diagonalizing to solve a linear recurrence with complex eigenvalues

I know how to solve for a closed form of linear recurrences whose matrix form has all real eigenvalues. What is the difference when solving one with complex eigenvalues? I can't seem to get this ...
4
votes
1answer
567 views

How to find recurrence relation of a given solution.

Determine values of the constants $A$ and $B$ such that $a_n=An+B$ is a solution of the recurrence relation $a_n=2a_{n-1}+n+5$. I know that the characteristic equation is $r-2 = 0$ which has the root ...
0
votes
1answer
86 views

Predicting future numbers in a sequence, using linear algebra,

We have several sequences, $x_k$, that satisfy the recurrence relation $$x_{k+1} = a_kx_k + b_kx_{k-1} + x_{k-2}.$$ We do not know the numbers $a_k$ or $b_k$, but they are the same for each ...
0
votes
1answer
32 views

Find a recurrence to count paths in a directed graph

Suppose we have an unweighted directed graph with vertices numbered as $1...n$ From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$. My task is to find a recurrence $f(i,j)$ to compute the ...
0
votes
2answers
28 views

Solving a nonhomogeneous recurrence relation

How does one solve a recurrence relation of the kind $u_{k+1} = u_k + u_{k-1} + a \cdot \cos(\omega k)$ for arbitrary $a > 0$ and $\omega > 0$?
6
votes
1answer
106 views

This 1 innocent looking recurrence relation seems to have no solution.

$$P(cx) = \cos(x) P(x)$$ For $c=2$, $P(x) = \sin(x)/x$ is a solution to this. I don't know if there's a closed-form solution for $c \ne 2$. Rather than add my own attempt at solution, which is ...