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

learn more… | top users | synonyms

2
votes
0answers
171 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
71 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
439 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
66 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
258 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)$ ...
1
vote
0answers
15 views

Explicit formula for inverse function for n-th partial sum of harmonic series

Originally, I was trying to work out an explicit formula for a function with the property that $f(x + \frac{1}{f(x)}) = f(x) + k$ for some $k$. This is inspired by a thing I did with a metronome ...
1
vote
0answers
21 views

Asymptotic behaviour of two dependent recursive sequences

I have two sequences whose relation is described in the following recurrence relations: $ p_{k + 1} = p_k + \frac{1}{2s_k}$ $ s_{k + 1} = s_k + \frac{s_k}{p_{k+1}}$ (when $p_0=2, s_0 = ...
1
vote
0answers
41 views

Recurrence relation for Binary String Question

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is: "Given an infinite length random binary string, what is ...
1
vote
0answers
28 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...
1
vote
0answers
30 views

Complex numbers product and ratio, prove this relation.

Define a table $T$ as follows: $$\text{If}\; n\geq k \; \text{then} \; T(n,k) = (2+3 i) \sum _{i=1}^{n-1} T(n-i,k-1)+(5+7 i) \sum _{i=1}^{n-1} T(n-i,k) \; \text{else} \; T(n,k) = 0$$ Then take rows ...
1
vote
0answers
29 views

Possible to determine if a more 'compact' solution to a linear recurrence exists?

Given a linear a recurrence relation. It is possible to express a solution in terms of summations, products, and the coefficients which appear in the recurrence. For example, in the case of a single ...
1
vote
0answers
39 views

General Solution to Linear Difference Equation: Is this correct

Notation: Let $$Q_1[f(x)] = \lim _{h \rightarrow 1} \frac{f(x + h) - f(x) }{h}$$ And let $$Q_1^{-1}\left[f(x)\right] = G(x)|Q_1\left[g(x)\right] = f(x)$$ Consider the equation $$a_0(x) + ...
1
vote
0answers
73 views

Need help with these recurrence relations

I had received some challenging recurrence last week, I did most of them except this and also one of its kind. It states Given $a_0=0$ and $a_1=1$, solve these recurrence relations: ...
1
vote
0answers
23 views

What [precisely] is special, algebraically, about fundamental Pell solutions?

I'm asking for a list of algebraic identities which "uniquely identify" (or nearly so) the fundamental solution (or those immediately around it) of a Pell equation. As a concrete [numerical] example, ...
1
vote
0answers
70 views

Recurrence Relation Challenges

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
1
vote
0answers
34 views

Finite geometric sequence with a ratio greater than 1

I am trying to solve the recurrence relation: $ t(n)= 3T(n/2)+Cn$ (if $n>2$) $t(2)=C$ (otherwise) I know that there is the Master Theorem but I am trying to use the tree method. This ...
1
vote
0answers
48 views

Proof that $\forall x \in \mathbb{R}, \forall n \in \mathbb{N}: (f(x))^n = f(nx)$ only has solutions of the form $f(x) = c^x$ for some constant $c$

I am looking for a proof (or a counterexample I suppose) that the recurrence equation (is that the right term here?) $(f(x))^n = f(nx)$ only has a solution of the form $ f(x)=c^x$ for some ...
1
vote
0answers
31 views

Solving a recurence system

Find a function $f(x,y) : \mathbb{N}^2 \to \mathbb{N}^2$ such that: $1 + f(x+1,y) - f(x,y) = a$ $1 + f(x, y+1) - f(x,y) = b$ $k + f(x-k, y) - f(x,y) = c \space \forall k \leq x$ $k + f(x,y-k) - ...
1
vote
0answers
30 views

Analytic Function Derived From Recursive Reverse Taylor Series?

Given the following recursive relation: $a_0 = 1,$ $a_n = a_{n-1}(p-2q)+2(-p)^n$ is there a simple function that has this as its Taylor series, i.e. $f(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!}x^n$ ...
1
vote
0answers
36 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 ...
1
vote
0answers
27 views

Deriving recurrence relations, very stuck!

Going through past papers for my exams and cannot figure this one out, does anyone know how to do these? The Bessel functions of integer order, Jn(x), are described by a generating function of the ...
1
vote
0answers
41 views

Monotonicity of a recursively defined sequence $s_{n+1} = \sqrt{4s_n -1}$

I am trying to answer this question: Let $s_1 = k$ and $s_{n+1} = \sqrt{4s_n -1}$. For what values of $k$ will the sequence $s_n$ be monotone increasing? I know the definition of monotone increasing ...
1
vote
0answers
62 views

Solving a Recurrence Relation With Summation and Tau Function

How can I solve the following: $$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$ Where $d(n)$ is the Tau function, and v is the set of values dividing n. e.g. $d(18) = ...
1
vote
0answers
47 views

Solution to a recursion relation.

Let $\beta >0 $. The question is to solve a following recursion: \begin{equation} P^{(j+2)}(\beta) = \frac{\imath}{2} \left[ \left((-1+\beta) j - 1\right) P^{(j+1)}(\beta) + ...
1
vote
0answers
33 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...
1
vote
0answers
21 views

Analyzing a recurrence model: equilibriums, stability and periodic behavior.

In orer to increase my knowledge in math I decided to analyze the following recurrence relation (logistic growth in ecology) $$N(t+1) = N(t) (1 + r(1-\frac{N(t)}{K}))$$ I found the equilibriums by ...
1
vote
0answers
61 views

May someone tell me where I went wrong when finding a closed-form solution to a recursion?

Let $r(n)=\left\lceil\frac{n}{4}\right\rceil$, where $k \in \mathbb{N}$. Note that this can be rewritten as a recursion $R(n)=R(n-4)+1$, where, $R(0)=0, R(1)=1, R(2)=1, R(3)=1$. Since this recursion ...
1
vote
0answers
35 views

Recurrence of a function

Consider the following recurrence: $$ T(n) = 2T(n/2)+n\lg n$$ Let’s use a base-case $T (2) = 2$ and let’s assume $n$ is a power of $2$. (a) “guess and prove by induction” method, considering the ...
1
vote
0answers
37 views

Algorithms: Recurrence

Here's a problem that I am struggling with... If two algorithms A and B both solve the same problem. On an input of size $n$ Algorithm $A$ breaks it into $5$ pieces of size $n/2$, recursively solves ...
1
vote
0answers
402 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 ...
1
vote
0answers
76 views

What is common between difference operators and recurent relations?

They say that solutions of recurrence relations are combinations of exponential functions, the series like [1 a a^2 a^3 and etc]. I know that the difference operators have a matrix like ...
1
vote
0answers
45 views

How to derive recursive equation for expected discounted utility function?

I am trying to mathematically represent expected discounted utilities when the length of a lifetime is uncertain. $V_0$ is the expected discounted utility at $t=0$ and can be represented as such: ...
1
vote
0answers
42 views

Help Solving a Recurrence Relation with an Inverse Term

I am having a hard time generating a characteristic polynomial for a recurrence relation I thought of the other day, $a_n = a_{n-1} + \frac1{a_{n-1}}$. I am pretty familiar solving basic recurrence ...
1
vote
0answers
139 views

Help with find recurrence relation running time.

Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. ...
1
vote
0answers
77 views

substitution method for recurrence tree

If one has recurrence function - $$T(k) = 2T(k-1)+ \frac 1k$$ how can one determine the upper and lower bounds? For upper bound, I try use 'substitution method' and drew out recurrence tree, ...
1
vote
0answers
61 views

How to solve the recurrence relation $f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$ to find a closed-form solution?

A friend of mine gave me a math problem whose answer turned out to be $$f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$$ for some fixed $p$. I'm trying to find a closed-form solution to the ...
1
vote
0answers
43 views

Closed form of an inhomogeneous non-constant recurrence relation

I try to find a closed form for the $f_k$'s (at least for $f_1$) satisfying the following recurrence relation for any fixed $n>0$: $f_0 = 0$, $f_n = 0$, and $f_k = \frac{n}{2k}(f_{k-1} + f_{k+1} + ...
1
vote
0answers
65 views

looking for explanation behind solution for a 1st order recurrence relation.

In lecture, we covered 1st order recurrence relations and came up with a solution by inspection. I sort of see that we're finding the next term in the sequence by multiplying the initial condition by ...
1
vote
0answers
193 views

Recurrent relation for number of ways to get a balanced n-binary tree

In answering a question related to binary trees, I came up with the following recurrent relation: Base cases: $$ f \left (1 \right ) = 1 $$ $$ f \left (2 \right ) = 2 $$ Recurrent relations: $$ f(n) ...
1
vote
0answers
33 views

Whether recursive relationship is a different version of principle of mathematical induction?

In connection with the question I can't get satisfied with such 'so on' type logic. Is there a better way to solve it? and the responses recieved I would like to know whether ...
1
vote
0answers
59 views

Solving a recurrence involving binomials.

Does anybody know how to solve the following recurrence? Maybe with generating functions? Any hint? $t(n) = 1 + \frac{1}{2^{n-1}} \sum_{i=0}^{n-1} {n \choose i} t(i)$
1
vote
0answers
36 views

Is there any way to solve the following recurrence relation in 2-dim with different boundary conditions?

I was trying to solve the following recursion problem. It seems like because of the different nature of the boundary conditions it is getting strange although I know the solution exists. The problem ...
1
vote
0answers
66 views

Deriving this recursive expression for Riemann Prime Counting Function?

Why does this work? $f(n,k,1)=0$ $f(n,k,j)= \frac{1}{k} - f(\lfloor\frac{n}{j}\rfloor, k+1, \lfloor\frac{n}{j}\rfloor) + f(n,k,j-1)$ Here, f(n,1,n) computes the Riemann Prime Counting Function. ...
1
vote
0answers
90 views

Scaling for characteristic polynomial of sequence of growing matrices

This is a follow-up question to Limit of sequence of growing matrices. There I was considering a sequence of matrices defined by $$ K_L = \left[H\otimes I_{2^{L-2}}\right]\left[I_2 \otimes ...
1
vote
0answers
59 views

Bounding a sequence defined recursively

Let $\{x_n\}$ be a sequence of positive numbers and $\alpha \in (0,1)$. Let $y_0 := x_n$ and $$ y_k := (\alpha \,y_{k-1} + 1-\alpha) x_{n-k} $$ for $k=1,2,\dots,n-1$. Is it possible to give a sharp ...
1
vote
0answers
85 views

genealogy pedigree chart

What is the simple expansion of a (simple) genealogy pedigree chart, where each person (only) has 2 parents? What is that called? Is it an arithmetic progression, or a geometric progression? You start ...
1
vote
0answers
282 views

A recurrence relation for Stirling numbers (2nd kind)

It is well-known that the Stirling numbers of the second kind satisfy the following (vertical) recurrence relation: $$\sum\limits_{r=k}^n \binom{n}{r}S\left( r,k\right) =S\left( n+1,k+1\right) $$ ...
1
vote
0answers
215 views
1
vote
0answers
41 views

Recurrence with cases

$\def\left{\operatorname{left}}\def\right{\operatorname{right}}$I have the following recurrence with cases: $$ p(l, r, s) = 0.5 \cdot \left(l, r, s) + 0.5 \cdot \right(l, r, s) $$ ...
1
vote
0answers
104 views

Cycle of remainders

Let $N, K, W$ be natural numbers If I start from $R_0$, say any integer $r_0, 0 \lt r_0 \lt N$ and proceed with: $$R_j = ( R_{j-1} + K ) \mod W,\quad j=1,2, \dots$$ (that is the remainder of the ...