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

learn more… | top users | synonyms

0
votes
0answers
27 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
75 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 ...
0
votes
1answer
34 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 ...
0
votes
2answers
38 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
17 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
15 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
39 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
38 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
66 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
44 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
144 views
+50

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
466 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
58 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
24 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
33 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) = ...
2
votes
0answers
33 views

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

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
41 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
0answers
76 views

Comment on this Pi Formula? [on hold]

I compute Pi in my own way as follows: $$\frac{\pi}{2}=1+\frac{1}{1+\frac{1}{\frac{1}{2}+\frac{1}{\frac{1}{3}+\frac{1}{\frac{1}{4}+\frac{1}{\vdots}}}}}$$ and use ...
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
126 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
259 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$: ...
9
votes
2answers
457 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
38 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.$ ...
3
votes
1answer
67 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} = ...
4
votes
2answers
58 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
394 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
353 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
770 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
35 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
40 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
16 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
23 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
580 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
23 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 ...
5
votes
2answers
194 views

Dynamics of the repetitions of $f(z) = z^{2} +\frac{1}{4}$

This is probably a classic and most likely an easy question, but I was not able to find an answer. If we have the iteration $z_{n+1}=g(z_n)$, where $$g(z) = z + a z^{2},$$ with $a\ne 0$, then using a ...
4
votes
5answers
90 views

How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$

I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve: $$\begin{aligned} T(1) &= 0 \\ T(2) ...
0
votes
2answers
32 views

Finding the position at n?

This dance asks every performer to follow a precise sequence of steps: • Stage 0 : First, get away from obstacles by setting up your starting point at position 0 • Stage 1 : Take one step forward ...
5
votes
5answers
257 views

Prove that the sequence with $T(0)=1$ and $T(n) = 1 + \sum_{j=0}^{n-1}T(j)$ is given by $T(n)=2^n$

$T(0)=1 \\ T(n) = 1 + \sum_{j=0}^{n-1}T(j) \\ $ Show that $T(n) = 2^n$. I know how to prove this by induction, but I would like to know how to show this using first principles. Edit: The way I want ...
5
votes
0answers
81 views

Sum of infinite series defined recursively

Suppose $s$, $t$, and $\delta$ are constants satisfying $0<s<t<1$ and $\delta>1$. An infinite sequence $\{y_k\}_{k=1}^{\infty}$ defined as follows: The initial term, $y_1$, is the ...
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
1answer
26 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
1answer
28 views

non-homogenous recurrence relation, with split boundary conditions

I have non-homogenous recurrence relation: $x_{t+1}=\alpha x_t+\beta x_{t-1}+\gamma$ with the following boundary conditions: $x_2=\alpha x_1+\gamma$ $x_{T}=1/2x_{T-1} +1/2$ Anyone know how to ...
0
votes
1answer
124 views

Backwards Recurrence [duplicate]

For $$I_n = \int_0^1 \frac{x^n}{x + \alpha}\,{\rm d}x$$ $\alpha$ constant parameter We know $I_0$ = log[ $\frac{1 + \alpha}{\alpha}$] and we can derive a recurrence formula for $I_n$: $I_n = \frac 1n ...
2
votes
1answer
57 views

Recurrence - using power series

Could you help me in solving this recursion( a closed form ) using power series $\mu(n)=\mu(n−1)k_0+(n−1)\mu(n−2) k_1 \tag 1$, where $k_0,k_1$ are constants $\mu(0)=3,\mu(1)=5$ HINT: We can think ...
27
votes
3answers
522 views

Finding every $n$ such that $a_n$ is an integer

Let us define $\{a_n\}$ as $a_1=a_2=1$,$$a_{n+2}=a_{n+1}+\frac{a_n}{2}\ \ (n=1,2,\cdots).$$ Then, is the following conjecture true? A conjecture : If $a_n$ is an integer, then $n\le 8$. I ...