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

learn more… | top users | synonyms (2)

2
votes
0answers
53 views

How to solve this tough recurrence relation?

For solving a related probability problem, I'm required to solve the following recurrence relation:- $q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times ...
2
votes
0answers
26 views

Deriving a recurrence equation and apply Master's Thrm to it

So for a function such as: function Hi(n) if n > 1 then for j ← 1 to n do print(”Hi”) Hi(n/2) Hi(n/2) Hi(n/2) It's very easy to eyeball this and get a ...
2
votes
0answers
34 views

Recurrence with Polynomial Coefficients of $n$

How would I solve or obtain a closed-form solution for 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 ...
2
votes
0answers
31 views

Solve the recurrence $T(n)=aT(n-1)+bn$

I have to solve the following recurrence, given $T(1)=1$, $$T(n)=aT(n-1)+bn$$ I have done the following: $$T(n)=aT(n-1)+bn \\ =a^2T(n-2)+ab(n-1)+bn \\ =a^3T(n-3)+a^2b(n-2)+ab(n-1)+bn \\ = \dots \\ ...
2
votes
0answers
17 views

Finding Recurrence Relation in Closed Form or as Infinite Summation/Coproduct

My recurrence relation is: $$f(n)=(2n-3) f(n-1) -x^2 f(n-2)$$ Where $$f(-1)=1$$ $$f(0)=0$$ $$f(1)=-x^2$$ $$f(2)=f(1)$$ $$f(3)=-x^2 (3-x^2)$$ And it gets more complicated from there
2
votes
0answers
75 views

A similar, but hopefully easier problem than Gilbreath's conjecture

Gilbreath's conjecture says that for every positive integer $n$, if we write out the first $n$ primes $2,3,5,7,11,13,\ldots,p_n$ take the differences between consecutive terms ...
2
votes
0answers
48 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
36 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
33 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
49 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
40 views

Infinitely many primes in second-order recurrence

I just wondered about the following question: Suppose that we are given a homogeneous second-order recurrence relation, $x_{n+2}+ax_{n+1}+bx_n=0$ for all $n\in\mathbb{N}$. Can we choose integers ...
2
votes
0answers
43 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
102 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
1k 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
259 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
37 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
112 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
83 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
120 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
73 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
54 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
81 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
131 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
106 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
73 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
762 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
341 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
294 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
190 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
507 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
285 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
359 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
102 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

Recursive definition of sequences inverse/equivalency.

So here's the problem: "Give a recursive definition of the sequence ($a_n$), $n = 1, 2, 3, ...$ if $a_n = 4n - 2$." Here's my answer:$$t_1 = 2; t_n = t_{n-1} + 4$$ However, I know this could also ...
1
vote
0answers
19 views

Recurence with multiple variables and functions

Is there an easy way to solve a recurrence given with two variables and three different functions? Actually I'm looking for the solution of: $$A(n,k)=A(n-2,k-1)+A(n-3,k-1)+R(n-2,k-1)+L(n-2,k-1) $$ ...
1
vote
0answers
16 views

Recurring Folds Through A Circle

If I were to cut a circular disk of paper, I would have a disk with one section. If I were then to fold it through its centre, I would have a disk with two sections (divided by the crease). If I were ...
1
vote
0answers
17 views

Discrete Model Finding Stability

For the discrete model $$x_{t+1} = (\lambda +1)x_t +x_t^3$$ Draw a bifurcation diagram (expressing the equilibrium vs $\lambda$ for values of $\lambda$ near zero. I have the bifurcation diagram. It ...
1
vote
0answers
42 views

partial fraction (with factoring involved) in recurrence relation problem

i want to factor the denominator of the function $f(x)=4-23x+21x^2/(1-2x-3x^2)(1-3x)$ so that it takes the form $(1-ax)(1-bx)(1-3x)$. What I've got is $4-23x+21x^2/(1-3x)(1+x)(1-3x)$ but the ...
1
vote
0answers
36 views

The recurrence $a(n,k) = \sum_{0\leqslant j<n} a(n+j,k-1)$

I'm trying to find a closed form expression to the following recurrence relation: \begin{align} &a(0,k) = 0, \quad \forall k\geqslant 1; \\ &a(1,k) = 1, \quad \forall k\geqslant 1; \\ ...
1
vote
0answers
19 views

Recurrence Relation / Difference Equation Problem

I am trying to solve the following recurrence relation, but I am doing something wrong all the time when trying to find the particular solution, and I cannot figure out what. ...
1
vote
0answers
21 views

Complexity of $T(n) = T(n-10) + \sqrt{n}$

I'm using the iteration method to find the complexity of the following recurrence (I can't use the master theorem because it doesn't match the MT form). $$ T(n) = T(n-10) + \sqrt{n} \text{ and } T(1) ...
1
vote
0answers
18 views

Deriving binomial distribution from a recurrence.

Let $X_n, n\geqslant1$ be iid random variables with distribution $\mathbb P(X_1=1)=p = 1 - \mathbb P(X_1=0)$. Let $S_0=0$ and $S_n=\sum_{i=1}^n X_i$, $n\geqslant1$. Let $q_{n,k}=\mathbb P(S_n=k)$, for ...
1
vote
0answers
27 views

Sequence from generating function.

Consider the recurrence $$\mu_1=1, \mu_2=2, \mu_3=4, \mu_4=8, \mu_5=16, \mu_6=32 $$ and $$\mu_{n+6} = \mu_n + \mu_{n+1} + \mu_{n+2} + \mu_{n+3} + \mu_{n+4} + \mu_{n+5}, n\geqslant 1. $$ The generating ...
1
vote
0answers
25 views

Did i multiply the sums correctly?

This is an extention to this question except i am unsure of whether i have done it correctly: $$ y'' = -y'(f(x) - r(x) y') $$ $f(x) = \sum_{n=0}^\infty s_n x^n$, $y = \sum_{n=0}^\infty a_n x^n$, and ...
1
vote
0answers
30 views

solve third order scalar using 3 by 3 matrix recursion

Suppose I have something like the following: $$t(n+2) = 3t(n+1) - 2t(n) + t(n-1)$$ I do not want a complete solution to this question. All that I would like to know is how to convert this into a 3 ...
1
vote
0answers
22 views

Did i generalize this series solution correctly?

$$ f(x) = \frac{y''}{p(x)y'} + r(x) y' $$ if all functions are expressed in their power series form, then: $$ y = \sum_{n=0}^\infty a_nx^n $$ $$ p(x) = \sum_{n=0}^\infty p_n x^n $$ $$ r(x) = ...