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

learn more… | top users | synonyms (2)

2
votes
0answers
43 views

Validity of approximating a difference equation with a differential equation

Consider the following difference-differential equation defined for positive integer indices $k$ and $t$: $$ A_k(t+1)-A_k(t)=\beta \frac{ A_{k-1}(t)- A_k(t)}{\alpha+2 t} + \delta_{k \beta} . \tag{1} ...
2
votes
0answers
31 views

How to solve a first order inhomogenous recurrence relation?

I have a recurrence relation for a fund that starts a 50 million, 6 % interest every year, and an outtake of 2 million/year. How to find out a solution for what funds exists after n years? ...
2
votes
0answers
30 views

Solution of partial difference equation

I want to find the explicit solution of the following difference equation $e_{i,j+1}=re_{i-1,j}+(1-2r)e_{i,j}+re_{i+1,j}+km_{i,j}$ where $r>0$, $k>0$ and $m_{i,j}$ are known and $e_{i,0}=0$. ...
2
votes
0answers
48 views

Recurrence Relation with $n^{\frac{1}{2^k}}$ Square Root

I tried to solve this recurrence relation, like the following: $$ \\ T(n) = \begin{cases} T(\sqrt[2]{n}) + c, & \text{if }n \geq 2 \\ a, & \text{otherwise} \end{cases} \\\\ T(n) = ...
2
votes
0answers
38 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
2
votes
0answers
101 views

How to solve a ceiling expression or recurrence equation?

I am trying to express the following in term of n, $$\underbrace{\hbox{$ \left \lceil \frac{3}{2}.\left \lceil { \frac{3}{2}.\left \lceil { \ldots \left \lceil \frac{3}{2}.\left \lceil { ...
2
votes
0answers
139 views

Special map $f(x_n)=x_{{n+1} [\mod 4]}$

As mentioned in the headline I am considering the map $f(x_n)=x_{{n+1} [\mod 4]}$. It looks a little bit similar to the dyadic (bernoulli) map but instead of $\mod 1$ we have $\mod 4$ which means that ...
2
votes
0answers
824 views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
2
votes
0answers
74 views

(limit of) a linear second order recurrence relation with variable coefficients

I have the following recurrence relation: $(n + 1) a_{n + 2} = (w (n + 1) - c) a_{n + 1} - z (n + 1)*a_{n}$ that I would like to either solve, or to get the $n$ goes to Infinity limit of the ratio ...
2
votes
0answers
253 views

Induction proof of a recurrence relation

I have some trouble with an induction proof for the following problem. There is a vending machine that only takes coins of value 1 and 5 respectively. Let $S_n$ be the number of different ...
2
votes
0answers
34 views

Determinant of Stirling submatrix

Consider the table containing the Stirling numbers of the second kind $S\left( n,k\right) $. From this table construct a square matrix $M$ containing $N$ differents rows from the table ...
2
votes
0answers
98 views

How to solve this recurrence relation (related to discrete Fourier transform)?

I am having trouble with the following recurrence relation: $$c_{n+1} - c_{n-1} = 2\alpha \sin \frac{(2n-1)\pi}{N} c_n, \quad\forall n \in \mathbb{Z},$$ where $N$ is odd and the initial condition is ...
2
votes
0answers
78 views

Recurrence relation for polygamma reflection polynomials

In the reflection formula for the polygamma function $$ \psi^{(n)}(1-z) + (-1)^{n+1}\psi^{(n)}(z) % = (-1)^{n} \pi \frac{d^{n}}{d z^{n}} \cot (\pi z) $$ the right hand side is a polynomial ...
2
votes
0answers
104 views

Showing the relationship between Lucas and Fibonacci numbers with a recursive relationship

Given the equation $$L_{n+k}-(-1)^kL_{n-k}=5F_kF_n$$ Where $\{L\}$ is the set of Lucas numbers and $\{F\}$ is a Fibonacci sequence, $n$ and $k$ are both $>0$ and integers, how would one develop ...
2
votes
0answers
71 views

How prove this sequences have limts and find this value?

let $f:R\longrightarrow R$,and $f(x)=x-\dfrac{x^2}{2}$,and $$L_{1}(x)=f(x),L_{2}(x)=f(f(x)),L_{3}(x)=f(L_{2}(x)),\cdots,L_{n}(x)=f(L_{n-1}(x))$$ and let $$a_{n}=L_{n}\left(\dfrac{17}{n}\right)$$ ...
2
votes
0answers
53 views

Finding the best real value for $C$.

Consider the recurrence $f_{n+1}=f_n + \ln(f_n)$ with $f_0=2$. Also consider differential equations of type $g(0)=2$ and $\dfrac{d g}{d x}=\ln(g(x)- C \cdot \ln(g(x)))$. Lets call the solution ...
2
votes
0answers
78 views

Solving recurrence relation of algorithm complexity?

Supposing I write an algorithm that results into this kind of recurrence relation $$\left\{ \begin{array}{ll} T(0)=T(1)=1 \\ T(n)=T\left(\lfloor n/2 \rfloor \right)+T\left(\lceil n/2 ...
2
votes
0answers
126 views

Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...
2
votes
0answers
104 views

Is there a closed form for this recurrence?

Given $$ E_{n,k} = \begin{cases} 0 & \text{ if } n \leq k \\ n & \text{ if } k = 0 \\ \sum_{i=0}^{n-1} \dfrac{1}{n} \cdot E_{i,k-1} & \text{ otherwise } \end{cases} $$ I wonder is there ...
2
votes
0answers
68 views

How much information do I gain from each modular inequality?

Problem details: Let $p = 2^{48}$, $s\leftarrow\{0,1\}^{48}$, and $a,b$ known constants. Furthermore let $f(x) = a x + b \pmod{p}$ and let the value $r_k$ be defined by the first-order recurrence ...
2
votes
0answers
55 views

how to compute $\lim_{n\to\infty}\ln(f(n))/\ln(n)$ for this given $f(n)$?

Let $c=f(0)$ be a real number and $n,m$ positive integers. Let $P_k(n)$ be integer polynomials of $n$. Let $f(n)$ be defined by the recursion $\left[\sum_{k=0}^{m} P_k(n)f(n+k)\right]+P_{-1}(n)=0$. ...
2
votes
0answers
683 views

Probability of tossing a biased coin without having k heads consecutively in a row

I got asked by a friend this question; I have a coin, the probability of receiving a head by tossing is $p$ and tail $1-p$. I have to toss it $n$ times without getting $k$ heads in a row. What is the ...
2
votes
0answers
301 views

Linear multivariate recurrences with constant coefficients

In the theory of univariate linear recurrences with constant coefficients, there is a general method of solving initial value problems based on characteristic polynomials. I would like to ask, if any ...
2
votes
0answers
266 views

Solving two-parameter linear recurrence with different initial values

I'm looking for a method to solve the well-known recurrence ralation with different initial values. The one-parameter linear recurrence is easier. Let's take a peek: $a_0 = \alpha$; $a_1 = \beta$; ...
2
votes
0answers
184 views

How to solve the recursive relation in Kalman filter?

I was wondering how to solve the Kalman filter's recursive equation (also see the appendix at the end of this post) for the estimated state $\hat{\textbf{x}}_{n|n}$ at time $n$, over discrete times ...
2
votes
0answers
75 views

Construction of polynomials with non-commutative elements.

I have a simple set of polynomials which I know how to construct for each integer $n$, but I havn't been able to write them down in terms of concrete sums and products. For $n\in\mathbb N_+$, we have ...
2
votes
0answers
487 views

recurrence relation with non constant coefficients

I'm trying to solve a second order differential equation and I got a recurrence. Can someone help to solve $$n(n-1+q)a_{n}-a_{n-3}+e\cdot a_{n-2}=0$$ where $q$, $e$, and $a_{0}$ are some real numbers ...
2
votes
0answers
69 views

On bounding the average cost of top-down merge sort

Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$ A_0 = A_1 = 0;\quad A_n = ...
2
votes
0answers
275 views

Bell-like recurrence

Let $$A(n)=\sum_{k=0}^{n-1}\binom{n}{k}A(k)+n!,\quad A(0)=1$$ $$B(n)=\sum_{k=0}^{n-1}\binom{n}{k}B(k)-n!-n!\sum_{k=1}^{n}\frac{1}{k!},\quad B(0)=-1.$$ I'm interested in computing $S(n)=A(n)+B(n)$ ...
2
votes
0answers
341 views

Gamblers ruin difference equation

I'm not sure where my mistake is in the following. Gambler starting with k dollars and playing a $50/50$ game where he increases in wealth by one dollar or decreases by one dollar until achieving $N ...
2
votes
0answers
99 views

Systems of partial difference equations

I would like to ask, if any general method of solving systems of partial difference (not differential) equations is known, at least for some classes of systems. For instance, for ordinary difference ...
1
vote
0answers
21 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
1
vote
0answers
24 views

Interesting recurrence equation models?

So I've had an introductory subject to recurrence equations and now I have to study a model using recurrence equations as a project. The problem is that most models I find are either elemental or ...
1
vote
0answers
15 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
1
vote
0answers
39 views

2nd order difference equation with n dependent coeff

I wanted to know if there was and solution to the following equation. $\left(N-n+1\right)E_{n+2} - NE_{n+1} + \left(n+1\right)E_{n} + N = 0$ Where $E_0 = 0$ and $E_1 = 2^N - 1$. $N$ is just a ...
1
vote
0answers
62 views

$T(n) = T(n/2 - \log(n)) +1$ using Substitution Method

I have the following recurrence: $$T(n) = T(n/2 - \log(n)) +1$$ How can this be solved using the substitution method? I don't fully understand the theory of this method and I'm not sure how to apply ...
1
vote
0answers
55 views

Solution of $x_{k+1} = x_{k} (a x_{k} + b)$

Could anyone help me to solve the equation $x_{k+1} = x_{k} (a x_{k} + b)$, for find the explicit solution of $x_{k}$? BTW. Do you know a GOOD book for the classification for non linear difference ...
1
vote
0answers
26 views

Calculate the total cost

According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: Cost per level $i \to \left( \frac{7}{8} ...
1
vote
0answers
21 views

Recurrence with Polynomial Coefficients of $n$

How would I solve a recurrence relation like $$a_n = f_1(n)a_{n-1} + f_2(n)a_{n-2} + ... + f_k(n)a_{n-k} + g(n)$$ where $f_1, f_2, ..., f_k, g$ are polynomials and $\left \{a_n\right \}$ is my ...
1
vote
0answers
52 views

Trace and transpose of a Matrix

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1 =sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2} =\frac{s}{n+2}\{ R_{n+1} ...
1
vote
0answers
25 views

Solution of ODE with initial values

Given data in the problem ${\psi'(t)}_{3 \times 3}=A_{3 \times 3}\psi(t)_{3 \times 3}, \psi(0)_{3 \times 3}=R^{cl}_{3 \times 3} \\ \phi'(t)_{3 \times 3}=t\hspace{.1cm}B_{3 \times 3} \phi(t)_{3 ...
1
vote
0answers
35 views

Recurrence relation sequence (Hard)

I was wondering if this sequence was possible using two base cases? The sequence is $\{-1,0,1,3,13\}$ .. Ive came close by doing $(a_{n-1})^2+a_{n-2}+a_n-1$ which works for everything but the $1$. I'm ...
1
vote
0answers
43 views

Difference equation of second order system with zero

I saw from lecture notes that difference equation of a first order system is like this: (1) (2) (3) (4) 1. What happens between (3) and (4)? It looks like inverse Z-transform but according ...
1
vote
0answers
14 views

What method to use to find a hypothesis of the solution of the recurrence relation?

Suppose that we want to find an asymptotic upper bound for a recurrence relation: $T(n)=aT \left ( \frac{n}{b}\right)+f(n)$ , $T(n)=c, \text{ when } n \leq n_0$, using the following method: We choose ...
1
vote
0answers
34 views

Recurrence Derivative

I have a recurrence relation as follows $ \left\{ \begin{array}{ll} R_0=H & \mbox{if } n = 0 \\ R_1(s)=sR_0 \hspace{.1cm} A & \mbox{if }n=1\\ R_{n+2}(s)=\frac{s}{n+2}\{ ...
1
vote
0answers
31 views

What does “combining the solutions in O(n) time” mean?

Algorithm $X$ proceeds by recursively solving $5$ subproblems of one-half the size, then combining the solutions in $O(n\log n)$ time. Algorithm $Y$ makes $9$ recursively calls on ...
1
vote
0answers
29 views

How to solve these recurrences

I have this recurrence and I have tried to solve it but I am completely lost. Master Theorem cannot be applied on this at-least not without some substitution or stuff. $ i)\quad T(n) = 4 T( \left ...
1
vote
0answers
70 views

What is the recurrence relation between $a_n, a_{n-1}$ , $a_n = \int_0^1 {x^n}\tan\left( \frac{\pi}{4}x\right) dx$

I would appreciate if somebody could help me with the following problem Q: What is the recurrence relation between $a_n, a_{n-1}$ ? $$ a_n = \int_0^1 {x^n}\tan\left( \frac{\pi}{4}x\right) dx,\ \ ...
1
vote
0answers
42 views

Non-recursive closed-form of the coefficients of Taylor series of the reciprocal gamma function

The reciprocal gamma function has the following Taylor series. $$\frac{1}{\Gamma(z)}=\sum_{k=1}^{\infty}a_kz^k,$$ where the $a_k$ coefficient are given by the followint recursion. $a_1=1$, ...
1
vote
0answers
33 views

Complicated 2-variable recurrence

I am analyzing some kind of construction for which size satisfies the following recursion: $P(n,k)=\frac{k}{2}\log \frac{k}{2} + 1 + \frac{n}{2} + P(\frac{n}{2},k) + P(\frac{n}{2},\frac{k}{2})$ ...