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

learn more… | top users | synonyms

2
votes
0answers
239 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
13 views

Almost complete multivariate recurrence solution…

$$ \gamma c_{jm_1m_2} = s^+_{jm_1}c_{j(m_1+1)m_2} - s^+_{jm_2}c_{jm_1(m_2+1)}\\ \gamma d_{jm_1m_2} = s^-_{jm_1}d_{j(m_1-1)m_2} - s^-_{jm_2}d_{jm_1(m_2-1)} $$ where $s_{jm_i}^{\pm} = ...
1
vote
0answers
23 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
36 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
58 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
40 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
30 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
19 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
58 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
30 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
31 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
258 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
60 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
38 views

finding a recurrence relation for tile covering problem

for $n \ge 1$ let $t_n$ be the number of ways to.cover the squares of a 2xn xheckerboard using 1x2 tiles which can be rotated (ie 2x1 tile) and 2x2 tiles. 1x2 tile comes in 5 different colors and 2x2 ...
1
vote
0answers
42 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
238 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
1
vote
0answers
35 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
113 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
73 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
39 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
63 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
163 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
31 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
55 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
32 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
61 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
81 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
58 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
76 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
266 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
197 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
96 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 ...
1
vote
0answers
71 views

Let $f(x+1) = P(f(x),x)$ where P is a polynomial. Express $f(x)$ as an integral.

Let $x$ be a real number and $f(x)$ a real analytic function such that $f(x+1) = P(f(x),x)$ where $P$ is a given real polynomial. Express $f(x)$ as an integral from $0$ to $\infty$. As an example we ...
1
vote
0answers
144 views

two dimensional recurrence

We have the following recurrence relation for $a_{n,m}$ $a_{n,m}=4a_{n+1,m-1}+\sum_{i=0}^{n-1}\sum_{j=0}^{m}a_{i,j}a_{n-1-i,m-j}$ with the boundary condition $a_{n,0}=c_n$ for $n\ge0$ where $c_n$ ...
1
vote
0answers
138 views

Evaluating iterated sine function

Let $f(x,1)=\sin(x)$ and $f(x,i)=f(\sin(x),i-1)$ ($f$ is the iterated sine function). For arbitrary $N$,$x_0$, how quickly can $f(x_0,N)$ be computed? Answer to this question discusses ...
1
vote
0answers
175 views

Closed form expression for a recurrence relation.

Hello, any ideas for computing closed form for a recurrence relation? In an attempt to compute what the $i$-th post order element would be in terms of its in order position in a complete binary tree, ...
1
vote
0answers
141 views

A recurrence relation

Motivated by a specific example, I have a rather general question to ask: suppose $a_n$ is a sequence defined by the relation $a_{n+1}=f_na_n+g_na_{n-1}$, $a_0=a>0$, $a_1=b>0$, where both $f_n$, ...
1
vote
0answers
70 views

Bivariate recurrence relation

Consider the following recurrence relation: $$A(h,0)=1\\ A(h,h)=c^h\\ A(h,r)=A(h-1,r)+(c-1)\cdot A(h-1,r-1).$$ Obviously, this is just a generalization of A008949, where $c=2$. Since I'm pretty sure ...
1
vote
0answers
150 views

Recurrence relation for the digits of the integer square root in binary

I was investigating a question on the Electrical Engineering Stack Exchange site, available here: ...
1
vote
0answers
134 views

Achieving the “mirror” of exponential decay

I'm working on a product that has a visual transition. I've found that applying a simple filter that results in an exponential decay (starting fast, then tapering off) is pleasing in one direction. ...
1
vote
0answers
138 views

recurrence relation of general difference polynomials

I have a sequence of difference polynomials (which I obtained by the method of finite differences) and I would like to find out if there is a recurrence relation between them. The generating function ...
1
vote
0answers
106 views

Find $G(n)$ with $n \geq 1$

Let $G(1) = 0, \ G(2) = 1$, $G(2n+1) = 2 + G(n) + G(n+1)$ and $G(2n) = 1 + G(n), \ \ n \geq 1$ Find $G(n) $ P.S: This is little problem in my problem. I tried to solve by using generating function, ...
1
vote
0answers
93 views

How to find the recurrence polynomial?

Problem: If $f$ is a polynomial with unknown roots $x_1,-x_1,x_2,-x_2\ldots,x_b,-x_b \quad (b \in \mathbb{N})$ and can be expressed as (known expansion): $$f(x)=\sum_{a=0}^{2b}f_ax^a\quad(b \in ...
1
vote
0answers
67 views

Recurrence $A_{n+1}=A_{n}+\mathbf{E}G_n$

This looks like a straightforward recurrence, but I have an impression I made a mistake somewhere. In this equation $G_n$ is a random variable $ G_n=\left\{ \begin{array}{c c} 0 & 1-p_n \\ ...
1
vote
0answers
175 views

Solve recurrence relation $a(n)=2\cdot a(n-1)+5\cdot a(n-2)+6\cdot a(n-3)$ and the associated cubic

I am trying to solve following : $$a(n)=2\cdot a(n-1)+5\cdot a(n-2)+6\cdot a(n-3)$$ with the initial conditions given by $a(0)=3,a(1)=2,a(2)=14$. So first of all, I want to mark that there exists ...
0
votes
0answers
15 views

Find solution to recursion relation

Consider a following recursion relation: \begin{equation} a_s^{(m+1)} = s a_s^{(m)} 1_{s \le m} + a_{s-1}^{(m)} 1_{s\ge 2} \end{equation} for $s=1,\dots,m+1$ subject to $a^{(1)}_1= 1$. The solution ...
0
votes
0answers
12 views

Series expansion in a recurrence relation (Lines in a plane)

L The recurrence is therefore L0 = 1 ; Ln = Ln−1 + n , for n > 0. The known values of L1 , L2 , and L3 check perfectly here, so we'll buy this. Now we need a closed-form solution. We could play ...
0
votes
0answers
23 views

Approximating the function $ f(x) = \frac{1}{1+a^2x^2} \text{with } a=4 \text{ in the interval }[-1,1]$ with Legendre Polynomials

Given: $$ f(x) = \frac{1}{1+a^2x^2} \text{with } a=4 \text{ in the interval }[-1,1]$$ Approximate the function $f(x)$ in the least squares sense using legendre polynomials up to order 2. The ...
0
votes
0answers
20 views

Non homogenous Recurrence Relation Problem

Consider the recurrence relation $$b[n] = b\left[ \frac{n}{2} \right] + b \left[ \frac{n+1}{2} \right] + 2$$ for $n > 1$ with $b[1] = 0$. Solve the recurrence in the case that $n$ is a power of $2$ ...