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

learn more… | top users | synonyms (2)

1
vote
0answers
17 views

Function of Difference/Summation and constrained indices

for fixed $n \geq 0$ (natural number) and $0 \leq i,j \leq n - 1$ i have this function for $0 \leq i + j \leq n - 1$ $$r(i,j) = \left( \sum_{l = 1}^{i + j - 1} l \right) + j$$ otherwise for $n \leq i ...
-2
votes
0answers
39 views

How to find recurrence relation for given sequence [on hold]

How do I find the recurrence of a sequence of : $1,\ 2,\ 1,\ 4,\ 6,\ 4,\ 17,\ldots$ where $T(1) = 1\\ T(2) = 2\\ T(3) = 1$
-1
votes
0answers
7 views

Research shows that I sell 2.45 times more of a unit online than I do in house [on hold]

The margin on in-house sales is 45% and my margin of online sales is 20%. Is it better to focus on online sales or in-house sales
0
votes
1answer
53 views

Cartesian coordinates for vertices of a regular polygon?

I'm trying to draw: A set of $N$ (edit) irregular polygons one inside the other, where the innermost should be an equilateral triangle, enclosed by a square, enclosed by a pentagon, etc. Where ...
2
votes
1answer
24 views

Finding the recurrence relation(with square roots) [on hold]

I came across a very peculiar recurrence relation : $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)} $ And Initial Condition $T(0) = T(1)= 1$ Any helps on how to find it
0
votes
1answer
22 views

Solution of recurrence relation for roots having multiplicity $ \ge 1 $

If there is a recurrence relation of the form $ a_n = c_1 a_{n-1} + c_2 a_{n-2}+ ... + c_k a_{n-k} $, then if b is a non zero complex root of the recurrence relation with multiplicity t, $t \ge 1 $, ...
0
votes
1answer
18 views

Obtaining z-transform of multivariate nonlinear difference equations

I need to obtain the z-transform of difference equations that are as follows: My problem however is multivariate and looks like this: $$ \begin{align} x_{k+1}&=ay_{k}+ x_{k}^2y_{k}\tag{1} \\ ...
1
vote
1answer
37 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. ...
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
1answer
32 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 ...
-1
votes
0answers
16 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
13 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
36 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?
2
votes
1answer
36 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
20 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 $$ ...
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
0answers
20 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 ...
-2
votes
1answer
26 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
4answers
39 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
45 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, ...
1
vote
2answers
19 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, ...
0
votes
2answers
18 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
3answers
64 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 ...
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 ...
1
vote
3answers
34 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
30 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
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 ...
3
votes
3answers
58 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 ...
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
2answers
26 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 : ...
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
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 ...
0
votes
1answer
87 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 ...
1
vote
1answer
31 views

Finding a Recurrence Relation.

This is from AMC 2015 . For each positive integer n, let S(n) be the number of sequences of length n consisting solely of the letters A and B, with no more than three As in a row and no more than ...
0
votes
1answer
34 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 ...
10
votes
1answer
152 views
+50

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

$$P(c \cdot x) = \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 ...
0
votes
0answers
26 views

How to find the period of a recurrence relation

Given the recurrence relation $s_{i+5}=s_{i+1} + s_i$ over $\mathbb{F}_2$ with initial states $s_0 = 1, s_1 = 1, s_2 = 1, s_3 = 0, s_4 = 1$ What is the best/quickest way to find the period of the ...
0
votes
1answer
49 views

variation to tower of hanoi problem

Here is the question: There are $m$ different sizes of disks and exactly $n_k$ disks of size $k$. Determine $A(n_l,. . . , n_m)$, the minimum number of moves needed to transfer a tower when ...
1
vote
0answers
31 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
1answer
63 views

strange fibonacci recurrence

As it is well known fibonacci numbers satisfy the recurrence relation $$F_{n}=F_{n-1}+F_{n-2}$$ with initial conditions $F_{0}=0$ and $F_{1}=1$. While playing around with numbers,I noticed the ...
1
vote
0answers
31 views

Proving recursive formula via induction leads to extra term?

I have been asked the following question, and despite spending the last 30 minutes on it, have not come up with a good result: Define f(1) = 2, and f(n) = f(n-1) + 2n for all n ≥ 2. Find a ...
0
votes
2answers
105 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: ...
1
vote
0answers
78 views

General formula of a sequence $a_{n+1} = 2a_n + 1/a_n$ [duplicate]

What is the exact formula for $a_n$ in the sequence $a_{n+1} = 2a_n + 1/a_n, a_1=1$? I discovered that there are no elementary answers, but I don't know how to solve it.
1
vote
0answers
26 views

Picard's theorem analogue for difference equations?

I am trying find bibliography on existence of solutions for difference equations but it seems that there is not much on the web. I need existence and bound of a certain nonlinear difference equation ...
0
votes
1answer
43 views

Converting equation into Octave / Matlab code and a for loop

I have an array of thousands of values I've only included three groupings as an example below: (amp1=0.2; freq1=3; phase1=1; is an example of one grouping) ...
1
vote
0answers
50 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 ...