# Tagged Questions

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

19 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 ...
65 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 ...
54 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 ...
37 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 ...
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 ...
35 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 ...
11 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 ...
29 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 ...
61 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 ...
32 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)$$ ...
40 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: ...
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 : ...
33 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 ...
36 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 ...
94 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 ...
33 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 ...
37 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 ...
230 views

### Does this functional equation have a non-trivial 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 ...
29 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 ...
59 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 ...
37 views

### Complicated recurrence relation

I would like to know if the following recurrence relation is solvable (\alpha_{1}n^{2}+\beta_{1}n+\gamma_{1})\ c(n+1)+(\alpha_{0}n^{2}+\beta_{0}n+\gamma_{0})\ ...
65 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 ...
33 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 ...
108 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: ...
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.
29 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 ...
52 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) ...
72 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 ...
81 views

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)$ ...
130 views

44 views

### Help fix this proof.

What is wrong with this proof? I followed the example of the answer to another one of my questions, here Define a general recurrence relation as $$f(x)^2=A(x)+B(x)f(x+n).$$ Substitute the root ...
26 views

### Closed solution to double recursion

I have a problem, where a subproblem is counting how many ways there are to interleave two words from disjoint alphabets while keeping the relative order of the letters within each word. For example, ...
27 views

### Recurrence Relation solution

How do I solve the following recurrence relation and what kind is it ? $a_n = a_{n-1} + c$ ? where c is constant Can this relation be considered non-homogenous as $F(n) = c.n^0$ ?
50 views

### Asymptotic Estimates for a Strange Sequence

Let $a_0=1$. For each positive integer $i$, let $a_i=a_{i-1}+b_i$, where $b_i$ is the smallest element of the set $\{a_0,a_1,\ldots,a_{i-1}\}$ that is at least $i$. The sequence ...
22 views

### $T(n) = 3T(n/3) + c$ using substitution, geometric series

so I have to find the asymptotic complexity of $T(n) = 3Tn(n/3) + c$ using either the substitution method, a recursion tree or induction. I used the Master Theorem to find an answer, but can't use ...
27 views

### Substitution method for solving recurrences

I see this in CLRS: We can use the substitution method to establish either upper or lower bounds on a recurrence. As an example, let us determine an upper bound on the recurrence ...