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

learn more… | top users | synonyms (2)

0
votes
1answer
21 views

Have the derivative of a function as a recurrence, looking for a closed form expression of the function.

I have a recurrence relation for the derivative of a function. Can anyone give me a closed form expression for the function? The is the derivative: $${\partial \over \partial x} f(x,z,a) = ...
0
votes
1answer
34 views

Analysis of Recursive Algorithms

So say I'm going to analyze a factorial function: pseudocode: F(n) if n=0 return 1 else return f(n-1)*n This is my basic operation: $F\left(n\:-\:1\right)\cdot n$ now when it comes to the ...
1
vote
1answer
37 views

Show that a recurrence relation is bounded

I'm studying the following recursive equation as part of my Economics class: $$k_{t+1}={k_t}^\alpha - c_t$$ For $t=0,1,2,...$, $0\leq \alpha<1$, and $k_0>0$ and $c_t\geq 0$ for every $t$. I ...
4
votes
1answer
51 views

Show that all solutions of this map tends toward infinity

Let $r≥4$ be a positive intger. Let us consider the difference non-autonomous equation: $$u_{n+1}=(1+r^{2n+1})u_{n}-r^{2n-1}u_{n-1}+2 \tag{*}$$ All solutions of $(*)$ have the form: ...
0
votes
0answers
41 views

Is this a proper way to inductively prove the theta bound of a recurrence relation?

Sorry for the messy work, but it's late. The problem at hand is to find and prove a theta-bound for the following recurrence relation: $T(n) = n{\frac{1}{2}}T(n^{\frac{1}{2}})+nlog(n)$ Claim: ...
0
votes
0answers
60 views

A sequence $x_n$ defined inductively by $x_{n+1}=F(x_n)$. Suppose $x_n\to x$ as $n\to \infty$ and $F'(x)=0$. Show $x_{n+2}-x_{n+1}=o(x_{n+1}-x_n)$.

Let a sequence $x_n$ be defined inductively by $x_{n+1}=F(x_n)$. Suppose that $x_n\to x$ as $n\to \infty$ and $F'(x)=0$. Show that $x_{n+2}-x_{n+1}=o(x_{n+1}-x_n)$. I'm not sure how to do this. Any ...
0
votes
1answer
24 views

How to solve this bivariate recurrence?

I have run into this recurrence relation while trying to solve a problem in probability. $$ g(r, s) = pg(r - 1, s) + qg(r, s - 1) $$ $$ g(0, s) = 1, g(r, 0) = 0 $$ So far I have concluded that $$ ...
0
votes
3answers
42 views

What is the greatest $b<1000$ for which 2015 is a member of a sequence $s_n$

Given a sequence of integers: $s_1=3, s_2=b$ and $s_{n+2}=s_{n+1}+(-1)^ns_n$ What is the greatest value of $b<1000$ for which the number 2015 is a member of the sequence? Justify your answer. So ...
0
votes
1answer
77 views

Sum from $i$ to $\lg(n)$

I am trying to find the solution for the recurrence equation using substitution : $$tn=3\cdot t(n/2)+n\quad \text{ where } \quad t1=1/2$$ for $n >1$, $n$ a power of $2$. I am stuck at $$tn = ...
1
vote
1answer
12 views

Assumption about the form of solutions to a recurrence relation

Basically, when solving such recurrence relations, we try to find solutions of the form $a_n = r_n$, where $r$ is a constant. $a_n = r^n$ is a solution of the recurrence relation $a_n = c_1a_{n-1} + ...
0
votes
1answer
43 views

Number of Delannoy paths that never go below the line $y = x$

How would I go about calculating $D(a,b)$ the number of such paths for some a,b. Say $a,b<=4$ and then express $D(a,b)$ in terms of another delannoy number? I have calculated $D(a,b)$ using a ...
0
votes
1answer
33 views

Avoiding piecewise definition for doubling and tripling alternatively

My data doubles, then triples, then doubles, then triples. I can't figure out how to write a function $f(N)$ for the data without using a piecewise function. Is it possible? Here is an example if ...
1
vote
1answer
77 views

Recurrence relation and deriving generating function

Let the sequence an be given by the recurrence relation $$a_n = −2a_{n−1} + 8a_{n−2}$$ $$a_0 = 1, a_1 = 5$$ (a) Calculate $a_2, a_3$ and $a_4$. (b) Derive an exact expression for the generating ...
5
votes
1answer
78 views

Find the limit of $a_{n+1}=\sqrt{7-(-1)^na_n}$

Find the limit of the following recurrence relation: $$a_{n+1}=\sqrt{7-(-1)^na_n}, n\geq 0$$ with $a_0=0$. I have thought that we can transform the relation to the following: ...
1
vote
2answers
39 views

Recurrence relation with reciprocal in a circuit

The motivation for this recurrence relation is to find the total resistance in this circuit: Assuming that the capacitor has no resistance, with only one loop of the circuit, (let us suppose) the ...
0
votes
0answers
16 views

Substitution method for solving recurrences - clarification

I'm trying to understand some details about the substitution method for solving recurrences. I'm using the Cormen et al book and there is a chapter of it available ...
2
votes
0answers
50 views

Convergence of difference equation to differential equation

Starting with the difference equation: $$f(x(t+dt),t+dt)= (1-a)f(x(t),t) + a f(x(t+dt),t)$$ where $x(0)$ is given and positive, $a\in(0,1)$, $f(0,t)=0$, and $f$ is increasing in both arguments. ...
0
votes
0answers
25 views

Prove that $b(i) > b(i-1)^{(i-1)}$ for some $i > i_0$ with $b(n) = 2^{b(n-1)}$

So I'm trying to prove that $b(i) > b(i-1)^{(i-1)}$ for some $i > i_0$ with $b(n) = 2^{b(n-1)}$ for some $i_0$, with $b(1) = 2$ and $i \in \mathbb{N}$. I have to admit, I haven't gotten very far ...
0
votes
0answers
21 views

Pertubative Solution To Vector Recurrence Relation?

Suppose we have the recurrence relation $$\mathbf{v}_n = F_n \mathbf{v}_{n+1},$$ where $\mathbf{v}_n$ is a sequence of $2\times1$ vectors, and $F_n$ is a sequence of $2\times2$ matrices. If $F_n=F$ ...
2
votes
1answer
54 views

Inequality with $\limsup$ and $\liminf$ of a sequence

$\{a_n\}_{n\in \mathbb{N}}$ is a sequence satisfying $a_0=1$ and $$a_n=\sum_{j=0}^{\lfloor n/2\rfloor}\frac{a_j}{(n-2j)!}\qquad n\ge 1$$ Show that $$\liminf_{n\to \infty}\frac{\ln a_n}{\ln n}\le ...
2
votes
3answers
86 views

Can $(2k-2)2^{k-1}$ be simplified to $(k-1)2^k$?

I'm working on solving some recurrence relations and following along with a couple of example solutions. One is my lecture notes. The other which closely matches in form is answered in this post: How ...
2
votes
1answer
45 views

A sequence related to squares of Fibonacci nubers

Let $f(n)$ be defined by $f(n)=f(n-1)+f(n-3)+f(n-4)$, for $n \ge 5$, $f(1)=1, f(2)=1, f(3)=2, f(4)=4$. First few terms of the sequence $(f(1), f(2), f(3), \ldots$) look like $(1, 1, 2, 4, 6, 9, ...
1
vote
1answer
72 views

Solving recurrence relation: $T(n)=2T(n-1)+1$, using recursion tree and substitution

Given this recurrence relation: T(n)=2T(n-1)+1, I am trying to find the tightest bounds possible. I have already figured the recurrence tree to look like this: Which would mean n levels, and 2^n ...
0
votes
0answers
30 views

prove by induction that T is increasing

I have following recurrence relation, $T(n) = T(\lceil\frac{n}{2}\rceil) + T(\lfloor\frac{n}{2}\rfloor) + f(n)$ with $f(n)\in \Theta(n)$ and the text book says that we can prove by induction that T ...
1
vote
0answers
43 views

What is the solution of this recursion, that's defined in terms of a sum, but with this $1$ odd twist?

$$ F(n) = \sum_{i=0}^{n} F\left(\left\lfloor\frac{i}{5}\right\rfloor\right) $$ I encountered this odd looking functional equation, while perusing the site yesterday. I'd be interested in seeing a ...
0
votes
1answer
27 views

Simplifying a fraction with exponent after variable substituion

I am trying to solve a recurrence relation using summation method. I'm following along some lecture notes and I don't understand this one part below. Given that $T(n) = 2T(n/2) + n\lg n$ setting $n ...
5
votes
4answers
469 views

How to find the general formula for this recursive problem?

I want to ask about recursive problem. Given: $$a_0= 11, a_1= -13,$$ and $$a_n= -a_{n-1} +2a_{n-2}.$$ What is the general formula for $$a_n$$ ? I've already tried to find the first terms of this ...
0
votes
0answers
30 views

Having trouble solving a complicated recurrence relation

Original equation: $T(n) = n^{2/3}T(n^{1/3})+n$ My work: = $n^{2/3}(T(n^{1/3})+n^{1/3})$ = $n^{2/3}(n^{2/9}(T(n^{1/3})+n^{1/9})+n^{1/3})$ = ...
2
votes
1answer
41 views

Solving recurrence relation using unrolling

I'm having a lot of trouble trying to solve a basic recurrence relation. $T(n) = 3T(n-5)$ T(x)= 1 for x<= 5 I feel like this problem could be solved by simply plugging in for T(n-5) in terms of ...
2
votes
2answers
238 views

Solving recursive formulas, proving with induction

I thought I had the answer to this problem but I seem to be off, something is wrong. The prompt: Find the exact solution to the following recursive formulas. You may guess the solution and then ...
2
votes
1answer
25 views

Prove by induction that the function $a(n)=5a(n-1)-6a(n-2)$ is equal to $2^{n}+3^{n}$ when a(1)=5 and a(2)=13

I'm having a bit of trouble proving this problem, as I'm not sure what to do at a specific step. For the sake of brevity I'm going to skip the base step where you prove that the original case is ...
-5
votes
1answer
84 views

How to solve recurrence relation using matrices? [closed]

How to solve these kind of recurrence relations using matrices: $$A_{n+1} = \sqrt 2 (A_n + B_n) - \sqrt 3 (A_n - B_n)$$ $$B_{n+1} = \sqrt 2 (A_n - B_n) + \sqrt 3 (A_n + B_n)$$ with initial ...
0
votes
1answer
33 views

General solution to difference equation with only one unique eigenvalue

If you have a system of difference equations like this: $x_{n+1} = a_{11}x_n + a_{12}y_n$ $y_{n+1} = a_{21}x_n + a_{21}y_n$ And you know that there is only one unique eigenvalue (ie: ...
0
votes
1answer
56 views

divide and conquer recurrence iteration

I am currently studying Divide and conquer. I have been reading algorithm design by Jon Kleinberg along with the lecture slides from our lecturer. I am stuck with the part where they teach us about ...
4
votes
3answers
194 views

BMO2 2001 Question 1 Recurrence Relation

Ahmed and Beth have respectively $p$ and $q$ marbles, with $p > q$. Starting with Ahmed, each in turn gives to the other as many marbles as the other already possesses. It is found that after $2n$ ...
2
votes
2answers
63 views

Solve the recurrence relation: $T_n=\sqrt nT_{\sqrt n} +1$

Try to solve it over similar methods , but I can not give the answer $T_n=\sqrt nT_{\sqrt n} +1$ Can anyone arrive at the solution?
0
votes
0answers
28 views

Efficient approximation of nth term without losing accuracy

Probelem Given a recurrence relation for gn as g0 = c where is a contant double. gn = a* gn-1 + b* gn-2 then find the value of another recurrence given by hn = gn/exp(n) constraints: 1 ...
0
votes
1answer
35 views

How to derive formula for second-order divided difference from a naive calculation?

I'm trying to study polynomial interpolation for my numerical analysis course, but I've become absolutely stuck in proving deriving the second order divided difference for myself: Assuming we have ...
0
votes
4answers
30 views

How did the solution to this system of equations get a power of n?

I have been reading up on how to solve problems relating to ideal gases. In a certain example problem in the book, Questions and Problems in school Physics by Tarasov and Tarasova, a system of ...
1
vote
1answer
28 views

Function of Difference/Summation and constrained indices

for fixed $n \geq 0$ (natural number) and $0 \leq i,j \leq n - 1$ i have this function for $0 \leq i + j \leq n - 1$ $$r(i,j) = \left( \sum_{l = 1}^{i + j - 1} l \right) + j$$ otherwise for $n \leq i ...
0
votes
1answer
118 views

Cartesian coordinates for vertices of a regular polygon?

I'm trying to draw: A set of $N$ (edit) irregular polygons one inside the other, where the innermost should be an equilateral triangle, enclosed by a square, enclosed by a pentagon, etc. Where ...
2
votes
1answer
36 views

Finding the recurrence relation(with square roots) [closed]

I came across a very peculiar recurrence relation : $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)} $ And Initial Condition $T(0) = T(1)= 1$ Any helps on how to find it
0
votes
1answer
45 views

Solution of recurrence relation for roots having multiplicity $ \ge 1 $

If there is a recurrence relation of the form $ a_n = c_1 a_{n-1} + c_2 a_{n-2}+ ... + c_k a_{n-k} $, then if b is a non zero complex root of the recurrence relation with multiplicity t, $t \ge 1 $, ...
0
votes
1answer
54 views

Obtaining z-transform of multivariate nonlinear difference equations

I need to obtain the z-transform of difference equations that are as follows: My problem however is multivariate and looks like this: $$ \begin{align} x_{k+1}&=ay_{k}+ x_{k}^2y_{k}\tag{1} \\ ...
1
vote
1answer
86 views

Why does my induction proof of an algorithm's running time always seems tautological?

I'm having some trouble proving algorithm's running times. The problem is not so much that I can't define the recurrence in open form nor that I cannot come to the conclusion that I know to be true. ...
0
votes
0answers
26 views

recurrence relation for Strassen's matrix multiplication

Let $a$ and $b$ be constants. Solve the following recurrence relation for $T(n)$: $$T(n)= \begin{cases}7T\left(\frac{n}{2}\right)+ an^2 & n>2 \\ b & n \le 2\end{cases}$$
1
vote
2answers
44 views

Why distribution of multiple recursive random number generators is uniform?

I was reading the article of L'Ecuyer on random number generation. The title of this article is "Uniform Random Number Generation". One of the proposed PRNGs there, is multiple recursive random ...
1
vote
0answers
13 views

constant coefficient difference equations LTI, why do I need the initial conditions?

Consider the following difference equation $$y_{n}=-\sum_{k=1}^{q}a_{k}y_{n-k}+\sum_{m=0}^{p}b_{m}x_{n-m}$$ I know that this is supposed to be LTI iff $y_{-q}=y_{-q+1}=\cdots=y_{-1}=0$. How does one ...
1
vote
1answer
39 views

Proof for the fact that the method of characteristic equations is a valid method to solve recurrence relations

Could someone kindly point me to a proof of the fact that the method is characteristic equations is a valid way of solving recurrence relations? It seems fairly arbitrary to me. I would be grateful ...
-2
votes
3answers
43 views

Solving recurrence relation using Master Method

How to solve following recurrence relation?? $T(2n) = T(2n-20) + n.$ And if there is any other way despite Master's method to do this simpler way, what is it?