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

learn more… | top users | synonyms

3
votes
2answers
78 views

If a recursive sequence converges, must its inverse be divergent?

Suppose I have a recursive sequence $\displaystyle a_{n+1} = \frac{a_{n}}{2}$. Clearly, the sequence converges towards zero. Now, suppose I define an "inverse" sequence $\displaystyle b_{n+1} = ...
0
votes
2answers
87 views

Meaning of 'expected value' in the following problem

Ok, I have found an interesting probabilites problem on TopCoder. I have truncated the statement: "What is the expected number of dice throws needed to attain a value of at least n (candies, in this ...
1
vote
1answer
29 views

Problematic Initial Condition of a Recurrence Relation

I encountered this equation, and tried to solve it: $T(n) = T(\sqrt{n})+log(n)$ Under the initial condition T(1)=1. Can someone tell me why is this initial condition helpful? I mean, of course ...
3
votes
2answers
397 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
0
votes
3answers
50 views

Differentiate a recurrence relation

How do I calculate the derivative of an equation like: $z_n = (z_{n-1} + c)^2$ with respect to $n$ where $z_0 = 0$ and $z,c \in \mathbb{C}$ I suspect that, for a given $z$, the derivative is not ...
2
votes
1answer
28 views

Intersection of two recurrences.

I have two sequences obtained by recurrences: $$f(0) = 1, f(1) = 9, f(n+2) = 10f(n+1) - f(n)$$ $$g(0) = 1, g(1) = 7, g(n+2) = 6g(n+1) - g(n)$$ How can I prove that apart from $f(0) = g(0) = 1$, these ...
4
votes
4answers
81 views

Homework | Find the general solution to the recurrence relation

A question I have been stuck on for quite a while is the following Find the general solution to the recurrence relation $$a_n = ba_{n-1} - b^2a_{n-2}$$ Where $b \gt 0$ is a constant. I don't ...
1
vote
1answer
30 views

Algorithm for retrieving all the permutations (randomized) for a vector sequence 1…N with only unique values

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$). I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
11
votes
5answers
723 views

How to deduce a closed formula given an equivalent recursive one?

I know how to prove that a closed formula is equivalent to a recursive one with induction, but what about ways of deducing the closed form initially? For example: $$ f(n) = 2 f(n-1) + 1 $$ I know ...
0
votes
1answer
32 views

Analyze the following recurrence relation.

I'd like to express the following recurrence relation as the number of multiplications it performs, and then again but this time as the number of additions/subtractions it performs. ...
-1
votes
0answers
28 views

Particular solution for Inhomogeneous recurrence [on hold]

I have solved quite a few recurrence problem and they're not that difficult, however I always hit a wall with particular solution. I just don't know what to do so I would like somebody to explain me ...
2
votes
2answers
24 views

MNTILE SPOJ Tiling patterns

We have tiles of size 2 * 1. We need to arrange the tiles to get the floor size of m * n. For ...
2
votes
1answer
29 views

Recurrence relation from code

My Friends, Hi, I see an old book in mathematics for computer science. everyone could help me, for example how we calculate the order (Time complexity) of following code: ...
0
votes
0answers
31 views

Extensions by recursive definitions

In the Wikipedia entry on Extension by definitions I learn that an explicit definition in the language of a theory $T$ yields a conservative extension $T'$ of $T$. I wonder if this eventually does ...
1
vote
2answers
45 views
1
vote
3answers
77 views

Show that $I_{12}\ne-0.0189$

For $n=1,2,3,\ldots$, let $$I_n=\int_0^1 \frac{x^{n-1}}{2-x} \,dx.$$ The value taken for $I_1=\ln2$ is $0.6931.$ If the recurrence relation is now used to calculate successive values of $I_n$ we find ...
2
votes
1answer
47 views

Height of Recursion Tree for $T(n, k) = T(n/2, k) + T(n, k/4) + kn$

If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$ What is the height of the recursion tree? Any idea or solution highly ...
1
vote
2answers
44 views

Solving a recurrence relation with square root

I ran into a bad recurrence relation. Anyone would calculate T(n) or add some hint? $$T(n) = \begin{cases} n,\quad &\text{ if n=1 or n=0 }\\ \sqrt{1/2[T^2(n-1)+T^2(n-2)]+}n ,\quad ...
0
votes
0answers
19 views

Solving a recurrence relation with absolute values in it.

The recurrence relation is: Let $\{y_{j}\}_{j\in \mathbb{N}}$ be a sequence of integers and x a real number then define: $P_{1}(x):=y_{1}+(-1)^{1}|x-y_{1}|$ and the general j-step as ...
0
votes
1answer
18 views

What's time complexity of algorithm for “Word Break”?

Word Break(Dynamic Programming) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible ...
4
votes
1answer
45 views

Period doubling bifurcation in a quadratic map

I am attempting the find $\mu$ for which the map $$x_{n+1} = \mu + x_n^2$$ undergoes a period doubling bifurcation. I understand that finding the fixed points of the map is the first step towards ...
1
vote
1answer
41 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
3
votes
0answers
82 views

After how many steps can compositions of $x\mapsto x+1$ and $x\mapsto x^2+1$ produce the same result starting from $1$ and $3$?

This problem is from a Turkish contest: Let $P(x)=x+1$ and $Q(x)=x^2+1$. Consider all sequences $(x_k,y_k)$ such that $(x_1,y_1)=(1,3)$ and $(x_{k+1},y_{k+1})$ is either $(P(x_k),Q(y_k))$ ...
1
vote
1answer
46 views

Two sequences defined by recurrence relations satisfy $x_n/y_n<\sqrt{7}$ for all $n$

Let $(x_n)_{n\geq 1}$ and $(y_n)_{n\geq 1}$ be two sequences such that: $$x_{n+1}=x_n^2+1 \quad \text{ and } \quad y_{n+1}=x_n y_n$$ with $x_1=2$ and $y_1=1$ Prove that for all $n$ ...
0
votes
1answer
170 views

Bounding error when iterating a function

If I am iterating some function $f$ that goes to infinity as x goes to infinity with error $o(g(x))$, for example, is there anyway to bound the error? To be more specific, if I have some sequence ...
1
vote
3answers
467 views

Finding characteristic equation of problem and solve recurrence relation

I have a homework assignment to find the characteristic equation of the set which a(n) = the number of sequences of length n which can be build from ${1,2,3...8}$ but you can't have two even numbers ...
0
votes
1answer
63 views

Solving the recurrence relation $T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n$

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated. My solution is: $n=3^m \to ...
0
votes
0answers
25 views

n-th derivative of product

I am looking for a closed-form for the $n^{\text{th}}$ derivative of $$\beta_1 g_1 g_3 + \beta_2 g_2 g_3$$ if $$g_k^\prime = \alpha_k g_{k+1}$$ Here's what I have tried so far: \begin{align*} ...
2
votes
0answers
38 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) = ...
3
votes
0answers
36 views

Solving the recurrence $T(n)=4T(\frac{\sqrt{n}}{3})+ \log^2n$ [closed]

How we calculate the answer of following recurrence? $$T(n)=4T\left(\frac{\sqrt{n}}{3}\right)+ \log^2n.$$ Any nice solution would be highly appreciated.
2
votes
0answers
45 views

How to solve this finite-difference equation?

How to solve the following finite-differences equation: $$f(x) = f(x-1) + f(x-\sqrt{2}), \quad x\in [\sqrt{2}, +\infty) \,?$$ Let's say $f(x) = f_0(x)$ for $x \in [0, \sqrt{2})$ is a given function. ...
0
votes
1answer
46 views

General solution of a finite-difference equation with real non-commensurable differences.

How to find a general solution of the following functional (recurrence) equation: $$f(x) = c_1 f(x - a_1) + \dots + c_n f(x - a_n), \tag{1}$$ where $c_i, a_i$, $i = 1, ... n$ are arbitrary real ...
1
vote
2answers
46 views

Solve $T(n) = T(n-1)+\log^2(n)$

I was trying to solve $T(n) = T(n-1)+\log^2(n)$ using substitution method and variables substitution but I can't find the correct answer. My attempt: Let $m = \log(n)$ then $T(2^m) = ...
8
votes
1answer
128 views

Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$

Question: Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$. Attempt: If I'm not mistaken this does not match any linear homogeneous pattern, nor ...
1
vote
1answer
267 views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
10
votes
2answers
477 views

Exact probability of random graph being connected

The problem: I'm trying to find the probability of a random undirected graph being connected. I'm using the model $G(n,p)$, where there are at most $n(n-1) \over 2$ edges (no self-loops or duplicate ...
1
vote
1answer
40 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
4
votes
2answers
59 views

A $n\cdot n$ square grid problem?

I thought of this problem when I was playing a game called BINGO with my friend. The game basically is like this: Suppose $2$ people are playing the game(can be played with any no of people though). ...
1
vote
4answers
396 views

Solving a recurrence of polynomials

I am wondering how to solve a recurrence of this type $$p_1(x) = x$$ $$p_2(x) = 1-x^2$$ and $$p_{n+2}(x) = -xp_{n+1}(x)+p_{n}(x).$$ I am wondering, how could one solve such a recurrence. One way ...
5
votes
3answers
355 views

Determining if a recursively defined sequence converges and finding its limit

Define $\lbrace x_n \rbrace$ by $$x_1=1, x_2=3; x_{n+2}=\frac{x_{n+1}+2x_{n}}{3} \text{if} \, n\ge 1$$ The instructions are to determine if this sequence exists and to find the limit if it exists. I ...
1
vote
1answer
786 views

Legendre polynomials recurrence relation

How can i get? $$P_{n+1}=xP_n(x)-\frac{1-x^2}{n+1} P'_n(x)$$ $n>=0$ Also know as the leadder equation of the legendre polinomials i tried to use de recurrence relations as: ...
3
votes
2answers
37 views

Solving a Recursive equation, wrong options? [closed]

This is a very simple recursive formula. Are the options provided wrong? $$ T(n) = T\left(\frac{n}2\right) + 2 $$ with $T(1) = 1$. What's the solution when $n=2^k$ ($n$ is a power of $2$)? The ...
0
votes
1answer
41 views

Limit of recurrence relation $x_k= f(x_{k-1})$ for an increasing function $f:[0,1]\to[0,1]$

Is there a standard result out there that gives the following? It looks graphically like it must be true, but I'd like to appeal to a known result if possible. Let $f:[0,1]\to[0,1]$ be a continuous, ...
1
vote
0answers
18 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 ...
0
votes
0answers
25 views

analyticical solution of a Recurrence serie

I have the following recurrence relation: $L_N = L_x + \frac{1}{\frac{1}{L_r} + \frac{1}{L_{N-1}} }$ $L_0 = L_x +L_r$ If $L_x$ and $L_r$ are kept constant, I have no problem to find a solution to ...
0
votes
2answers
39 views

Solving a recurrence relation. Check my answer

I have a recurrence relation: T(n)=4 for n<=2 T(n)=3T(n/3)+5 for n>2 So I began solving it, ...
3
votes
2answers
595 views

Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

Fibonacci numbers $f(n)$ are defined recursively: $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$. They also admit a simple closed form: $$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt ...
0
votes
1answer
50 views

Finding the fixed points of a recurrence relation (and systems of) analytically?

How would I go about finding the fixed points of the following recurrence? $$X_n = 2X_{n-1}(2- 3X_{n-1}) + X_{n-1}$$ And therein, determining their stability analytically? Also, how does one find ...
1
vote
2answers
43 views

Prove by induction a formula for $x_{k+1}=\frac{x_k}{x_k+2}$, $x_1=1$

I have a IT Maths exam coming up and I just can't figure out this question. Any help would be appreciated thanks. A sequence of integers $x_1,x_2,\dots,x_k,\dots$ is defined recursively by ...
0
votes
0answers
24 views

Recurrence relation expressed as gamma funtions

Where can I find literature on solving recurrence relations expressing the nth term as a gamma function? I know this can be done for example with $\alpha_{k+1}=\frac{\alpha_{k}}{k+b}$ can be solved by ...