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

learn more… | top users | synonyms (2)

-1
votes
0answers
9 views

Linear Non-Homogeneous Recurrences - Guessing the particular solution

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
11 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
10 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
31 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
31 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
16 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
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 ...
-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
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, ...
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, ...
0
votes
2answers
15 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
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 ...
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
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
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
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 ...
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 ...
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
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 : ...
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
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 ...
1
vote
1answer
28 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
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 ...
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 ...
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
48 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
30 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
28 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
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: ...
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
25 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
42 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
43 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 ...
6
votes
1answer
78 views

Product of a Finite Number of Matrices Related to Roots of Unity

Does anyone have an idea how to prove the following identity? $$ \mathop{\mathrm{Tr}}\left(\prod_{j=0}^{n-1}\begin{pmatrix} x^{-2j} & -x^{2j+1} \\ 1 & 0 \end{pmatrix}\right)= \begin{cases} ...
1
vote
1answer
97 views

New idea to solve $\int x^n e^x dx$

I have this problem $$\int x^n e^x dx= x^ne^x -nx^{n-1}e^x +n(n-1)x^{n-2}e^x- \cdots+(-1)^nn!e^x $$ my try was to use integration by part . $$I_{n}=\int x^n e^x \, dx=e^x x^n -\int (nx^{n-1})e^x \, ...
1
vote
0answers
38 views

Can this combinatoric sum be simplified?

Base cases: $F(n,k,d) = 0$ if $d=0$ and $n>0$ $F(n,k,d) = 1$ if $n=0$ Expression: $$F(n,k,d) = \sum_{s=0}^{\min(k,n)}\binom{n}{s}F(n-s,k,d-1)$$ I am trying to compute the value of $F(n,k,10)$ ...
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\, ...
2
votes
2answers
48 views

Understanding two “triangular” sequences

Just playing around doodling today and I happened across two related sequences of numbers and I'm reaching out to understand what exactly is going on. Sequence 1 The $n$th term of Sequence 1, $a_n$, ...
8
votes
1answer
142 views

Does $a_0=0, a_1=1, a_{n+2}=2a_{n+1}-3a_n$ ever return to 1 or -1 for $n>3$?

The sequence in question is the Lucas or Generalized Fibonacci sequence A088137. It's easy to write down its generating function $\frac{x}{1-2x+3x^2}$ and an explicit formula $a_n = ...
0
votes
1answer
20 views

Number of ways 1a,1b,5 can add up to n (with this being a permutation)

This problem is on my homework. A vending machine dispensing books of stamps accepts $\$ $ 1 coins, $ \$1 $ bills and $ \$5 $ bills. A) Find a recurrence relation for the number of ways to deposit n ...
4
votes
2answers
49 views

Is there any way to compute these sums quickly?

I have a sum of the following form (all numbers are positive integers): $$F(p) = \sum_{x=1}^{N} a_x x^p $$ Where $N$ and all $a_x$ terms are known/fixed constants. However I need to be able to ...
4
votes
1answer
122 views

How to solve this nonlinear difference equation $a_{n+1} = 2a_n + \frac{1}{a_n}$, $a_1 = 1$? [duplicate]

How to solve this nonlinear difference equation $$a_{n+1} = 2a_n + \frac{1}{a_n},\quad a_1 = 1.$$
2
votes
2answers
59 views

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$?

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$ , I don't have an idea for solve the question. My attempt : $\frac{T(n)}{\sqrt {n}}^2 =99T(\sqrt {n})+100 $ and $\ s(k)= ...