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

learn more… | top users | synonyms (2)

1
vote
1answer
31 views

Why does my induction proof of an algorithm's running time always seems tautological?

I'm having some trouble proving algorithm's running times. The problem is not so much that I can't define the recurrence in open form nor that I cannot come to the conclusion that I know to be true. ...
-1
votes
0answers
3 views

Obtaining z-transform of multivariate nonlinear difference equations

My research area is not Mathematics, but I am facing a conceptual mathematical issue, the answer to which I could not find in regular textbooks and other material that the internet fetched me and ...
2
votes
2answers
52 views

Recursive integration

The integral I have is $$I_{n} = \int^{\pi/2}_{0} \cos^{2n+1}y \ \mathrm{d}y$$ And I have found $I_{n} = \frac{2n}{1+2n}I_{n-1}$ but I want to express $I_{n}$ in a form without $I_{n-1}$ how do I do ...
0
votes
1answer
19 views

Why distribution of multiple recursive random number generators is uniform?

I was reading the article of L'Ecuyer on random number generation. The title of this article is "Uniform Random Number Generation". One of the proposed PRNGs there, is multiple recursive random ...
0
votes
0answers
11 views

recurrence relation for Strassen's matrix multiplication

Let $a$ and $b$ be constants. Solve the following recurrence relation for $T(n)$: $$T(n)= \begin{cases}7T\left(\frac{n}{2}\right)+ an^2 & n>2 \\ b & n \le 2\end{cases}$$
0
votes
2answers
17 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 ...
-2
votes
1answer
24 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
votes
0answers
13 views

Linear Non-Homogeneous Recurrences - Guessing the particular solution [on hold]

why does one need to multiply the particular solution of the function $4\cdot7^n$ with n, but this is not the case with $5 \cdot 2^n$. So what I'm asking is, why is the particular solution to $4 ...
1
vote
0answers
12 views

constant coefficient difference equations LTI, why do I need the initial conditions?

Consider the following difference equation $$y_{n}=-\sum_{k=1}^{q}a_{k}y_{n-k}+\sum_{m=0}^{p}b_{m}x_{n-m}$$ I know that this is supposed to be LTI iff $y_{-q}=y_{-q+1}=\cdots=y_{-1}=0$. How does one ...
0
votes
1answer
11 views

Proof for the fact that the method of characteristic equations is a valid method to solve recurrence relations

Could someone kindly point me to a proof of the fact that the method is characteristic equations is a valid way of solving recurrence relations? It seems fairly arbitrary to me. I would be grateful ...
-2
votes
3answers
35 views

Solving recurrence relation using Master Method

How to solve following recurrence relation?? $T(2n) = T(2n-20) + n.$ And if there is any other way despite Master's method to do this simpler way, what is it?
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
vote
1answer
41 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
33 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
18 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
62 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 ...
1
vote
3answers
942 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 ...
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
49 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
29 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
78 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
9 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
25 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
583 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
130 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
30 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: ...