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

learn more… | top users | synonyms (2)

2
votes
0answers
16 views

Need help in understanding the procedure of expanding recurrence formula

So here is the actual expansion: \begin{align} T(n) &= T(n-1) + n \\ &= T(n-2) + (n-1) + n \\ &= T(n-3) + (n-2) + (n-1) + n \\ &\vdots \\ &= T(0) + 1 + 2 + \ldots + (n-2) + (n-1) ...
2
votes
0answers
33 views

Why do I generally see real solutions to recurrence relations?

I haven't worked very much with recurrence relations, but for the ones I have worked with I always get real solutions, which is strange to me because looking briefly at the procedure for solving ...
2
votes
0answers
49 views

What techniques does Mathematica use to find solutions to these sequences?

This question is related to my previous question: Need help finding a closed form for complicated sum. An answer to that question led my to try and find the general term of the following recurrence: ...
2
votes
0answers
56 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
32 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
76 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
54 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
39 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
51 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
41 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
103 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
140 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
263 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
40 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
115 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
84 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
127 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
83 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
132 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
772 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
364 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
298 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
194 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
76 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
517 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
72 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
287 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
365 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
37 views

A question on generating function

How to find the generating function of $\binom{2n}{n}$?
1
vote
0answers
33 views

How to solve nonlinear recurrence relation (quadratic)

Please help me solve this weird recurrence relation. This is not really standard quadratic, so I'm totally confused. I tried with logarithm (but 8 is excess), tried writing this recurrence in one ...
1
vote
0answers
30 views

Generating Series and Recurrence Relation and Closed Form

We have the following recurrence relation: $b_n=2b_{n-1}+b_{n-2}$ and initial conditions $b_0=0, b_1=2$ I use the generating series method to solve as following: Let ...
1
vote
0answers
12 views

Deriving the Particular Solution to a Linear Discrete Dynamical System

In my lecture notes it says that for a linear dynamical system of the form $ f(x) = Ax $ where A is diagonalisable d x d matrix, with $ \left \{ v_1 , v_2, \cdots , v_d \right \} $ a basis for $ ...
1
vote
0answers
24 views

Linear recursions in finite fields

Let $F$ be a finite field and let $\alpha$, $\beta$ be distinct nonzero elements of $F$. Let $\alpha$ have order $r$ and let $\beta$ have order $s$. Let $M = \operatorname{lcm}(r, s)$. Let $a,b$ be ...
1
vote
0answers
13 views

How do we get $S(m) = S(m/2) + \lg m$ from $T(n) = T(\sqrt{n}) + \lg\lg n$?

I am confused about example we got today in class. Here is a recurrence and I am not sure how we got $S(m)=S(m/2)+(\lg m)$ $$T(n)=T(\sqrt{n}) + (\lg\lg n) $$ Let $$m =\lg n$$ $$S(m)=S(m/2)+(\lg m) ...
1
vote
0answers
26 views

Probability of winning a snooker-match

Suppose, a snokker match is best of $2n-1$, so the player who wins $n$ frames wins the match. Suppose, the probability for winning a frame is $p$ for player $1$. What is the probability ...
1
vote
0answers
22 views

Generating function of non-linear recursion

I'm just not able to understand how they got from where they substituted a subscript n after the second equals to sign from 5.27 to x(A(x))^2 Any help would be much appreciated.
1
vote
0answers
37 views

Multiple Anihilating Random Walks in a Ring (cycle)

I've been trying to solve this problem for a long time. Problem Let $R$ be a cycle with $2n$ nodes and assume there are $2k$ particles performing a simple random walk in this ring (i.e., they have ...
1
vote
0answers
16 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...