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

learn more… | top users | synonyms (2)

1
vote
1answer
92 views

Recursive Solution to Interest with Monthly Deposits

I open an account at a bank with 1% interest compounded monthly. I'm adding $100 to it at the beginning of each month (starting with month 1). (a) Set up a recurrence relation for the amount in the ...
1
vote
1answer
38 views

use substitution method to prove an equation is in O(n log2 n)

I am trying to prove that the equation: T(n) = 2T((n/2) +17) + n is O(n log_2(n)) I have to do this by using substitution ...
1
vote
2answers
60 views

How do you solve these recurrence relations for a closed form?

I'm not sure what methods are used to solve recurrence relations for a big-$O$ notation. Thinking about the problem conceptually doesn't really help me, but I feel like I could use some form of ...
1
vote
1answer
26 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...
1
vote
0answers
185 views

Method for deriving an Exponential Moving Average?

I have a formula for an exponentially weighted moving average function defined recursively as: $S_t = a*Y_t+(1-a)*S_{t-1}$ Where: $a\in (0,1)\cap \mathbb{Q}$ $t$ represents time $Y_t$ is the value ...
1
vote
0answers
73 views

Using a Recursion Tree to solve the recurrence $T(n) = \sqrt n T(\frac{n}{2}) + 10n$?

I am attempting to solve the above recurence by giving tight $\Theta$ bounds. Assume that the logs here are all base 2! To solve a recursion tree as far as I understand, I need two things. The ...
1
vote
2answers
43 views

Solving (for asymptotics) of certain recurrence equations.

I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. For example ...
1
vote
1answer
31 views

$g(n)=\sum_{i=0}^{n-1}g(i)g(n-i-1)$, and $g(0) = 1$, so which is $g(n)$?

I have an equation that: $g(n) = g(0)g(n-1)+g(1)g(n-2) + ... + g(n-2)g(1)+g(n-1)g(0)$ And I also know that $g(0)=1$. How can I derive the close form of function $g(n)$ ?
1
vote
1answer
69 views

Properties of a recursively-defined sequence using induction

This is a homework problem. Not expecting the solution, just a nudge in the right direction! $N$ is a function defined inductively as follows: $$N(1) = N(2) = N(3) = 1$$ $$N(n) = N(n−1) + N(n−3) ...
1
vote
0answers
12 views

Is there a way to express a closed form for a partial derivative of this recurrence relation?

Here's the relation: if $n\ge j:$ then $$ \sigma(n,j,d) = d \cdot\left( \log j-\sigma\left(\frac{n}{j}, 1+d, d \right)\right)+\sigma(n, j+d, d )$$ And here's the terminating condition if $n < j$ ...
1
vote
0answers
60 views

Finding Function Representation of Recursive Sequence

I was trying to find one of the roots of $x^2 + 4x + 3 = 0$ by deriving a continued fraction from the recursive formula $x = -3/x - 4$ (every step of the approximation you increase the recursion by ...
1
vote
0answers
138 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
41 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
1answer
34 views

Summation of series- substitution

If we have $\sum_{n=0}^{\infty}nf(n)=C, C\ne0\tag 1$, C is a constant, can we find a closed form for f(n)?. NB : Given condition is that $\sum_{n=0}^{\infty}f(n)$ converges to a constant value $K$ ...
1
vote
2answers
75 views

Summation of infinite series

If we know the series sum given below converges to a value $C$(constant) $$\sum_{n=0}^{\infty}a_n =C \tag 2$$ Can we generate following in terms of C. values of $a_n$ will tend to zero as n goes to ...
1
vote
1answer
80 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
36 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
1answer
30 views

Is it possible that a randomized recursion has a nonzero probability of either converging or diverging?

I have very little "hands-on" experience with probability, but here is my context: I was looking at the random Fibonacci sequence: $$f_0=f_1=1, f_n=f_{n-1}+Xf_{n-2}$$ where $X$ is chosen randomly ...
1
vote
0answers
49 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
65 views

Boundedness of solutions of Difference equation

Consider a second order difference equation in complex plane, \begin{equation} z_{n+1}=\frac{\alpha + \beta z_{n}}{1+z_{n-1}},\qquad n=0,1,\ldots \end{equation} where the parameters $\alpha, ~\beta$ ...
1
vote
0answers
37 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
50 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
1answer
84 views

Queuing theory-Multiple server (reducing simple recurrence formulas)

The equations given in 6.3 have been reduced which really eases the computation in further studies. But I tried to find the method of reducing these but I could not find a way at all. Any hints will ...
1
vote
0answers
78 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
1answer
200 views

Divide and Conquer (recurrence relation problem)…

The problem: (a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers. (b) Give a recurrence relation for ...
1
vote
0answers
20 views

Literature on functional difference equations

dear community. I'm looking for books/guides on functional difference equations. Can you recommend some? Below I try to explain what kind of equations I have in mind. As an example, one of the ...
1
vote
2answers
33 views

Finding the inhomogeneous solution [duplicate]

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would I find the inhomogeneous solution for this since the homogenous solution is 0 given initial conditions?
1
vote
0answers
35 views

Is there a better notation for difference equations?

Difference equations are quite messy to deal with, esp. in constraint optimization with many time subscripts that invite mistakes. Is there a better notation? Something like Feynman diagrams for ...
1
vote
0answers
29 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
136 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
82 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
1answer
37 views

Help with recurrence equation

I need to solve the following recurrence equation $p_i =\begin{cases} r(p_{i-1}+p_{i+2}) &\mbox{if } i \text{ is odd} \\ (1-r)(p_{i-1}+p_{i}) & \mbox{if } i \text{ is even} \end{cases} i ...
1
vote
0answers
33 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
2answers
43 views

Recurrence with multiplication

Let $\{a_{n}\}$ be a sequence of nonnegative numbers such that $a_{n} = 2^{n}a_{n - 1}^{3/2}$. If $a_{1}$ is sufficiently small, why must $a_{n} \rightarrow 0$ as $n \rightarrow \infty$?
1
vote
0answers
72 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
1answer
57 views

Solve $X_n=\lfloor \sqrt{X_n} \rfloor+X_{n-1}$

How do I solve $X_n=\lfloor \sqrt{X_n} \rfloor+X_{n-1}$? The initial terms are $1,2,3,5,7,10,13,17,21,26,31$. A search on oeis.org/ gave $\lfloor n/2 \rfloor\cdot\lceil n/2 \rceil$ + 1 which should be ...
1
vote
0answers
39 views

$\cos(2\arccos(\frac{a}{a+1})x$

I have trying to prove that this cosine map: $$\frac{r}{4}((a+1)\cos\left(2\arccos\left(\frac{a}{a+1}\right)\ \left(X_n-\frac12\right)-a\right)$$ is a logistic map. What I have done so far: Using ...
1
vote
1answer
56 views

Recurrence Relation all general solutions

I need some help solving the following recurrence relation: $a_n = 4a_{n-1} - 4a_{n-2} + (n+1)*2^n$ What I've tried: a) Find the general solution of the associated linear homogenous recurrence ...
1
vote
1answer
209 views

Solving recurrence relation: f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3

f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3 I have attempted to solve it by letting n = 2k f(2k) = 3f(2k-1) - 2f(2k-2) Then set S(k) = f(2k) S(k) = 3*S(k-1) - 2*S(k-2) ...
1
vote
1answer
33 views

third order recurrence relation with non-constant coefficients

Does anyone know of a paper that may have been written on $3^{rd}$ order recurrence relations with polynomial coefficients, that is, one of the form $$A(n)a_{n+3}+B(n)a_{n+2}+C(n)a_{n+1}=D(n)a_n$$ ...
1
vote
0answers
50 views

Closed form for a sequence defined recursively

Let $a_k$ be a sequence such that $a_0=0, a_1=0, a_2=1, a_3=1$ and $$a_{k+4}=-\frac{a_{k}+ka_{k+2}}{(k+1)(k+2)}$$ for $k\ge 0$. My question is: Is a closed form formula for $a_n, n\ge 4$ possible? ...
1
vote
1answer
40 views

Hypergeometric function relation knowing initial value?

Is there a relationship or recurrence relation I can use to solve for $$\, _2F_1(b,r+k;a+b+k;p)$$ as a function of $k$, with known value of when $k=0$ $$ \, _2F_1(b,r;a+b;p) = f_0$$ (a,b,r,p) are ...
1
vote
1answer
35 views

Does the order I multiply the characteristic equation's factors in the homogeneous solution matter?

I've been doing a recurrence relation exercise in my book. Doing some steps and comparing them to the ones taken by the book. $$T(0) = 1$$ $$T(1) = 2$$ $$T(k) - 7T(k-1)+10T(k-2)=6+8k$$ ...
1
vote
1answer
52 views

Derive recurrence relations for Bessel functions from the generating function

I'm going through practice questions for my exams but this question has left me confused: The Bessel functions of integer order, $J_n(x)$, are described by the generating function: Derive the ...
1
vote
0answers
35 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
55 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
78 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
1answer
186 views

Recurrence Question with Ternary String

Problem: Find a recurrence relation for the number of ternary strings of length n that contain at least one 0. Ternary string only contains 0s, 1s, and 2s. Approach: Assuming that the length n is ...
1
vote
0answers
58 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
44 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 ...