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

learn more… | top users | synonyms (2)

1
vote
0answers
44 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 ...
0
votes
1answer
54 views

On the existence/applications of infinitely-nested functions

Inside a previous question, one particular nested function shown is the known tetration. This "kind" of arbitrary repeated functions has always intrigued me, because inside their properties lie so ...
1
vote
1answer
43 views

Number of strings of size $k$ that do not have 'ab'

Consider $\Sigma = \{a,b,c\}$ and the language $L$, the set of all strings that do not contain 'ab' Find strings, of size $k$ is in $L$ ($L_k$) Consider $A_k$ (strings of size $k$ that end in $a$) ...
0
votes
0answers
44 views

Does $f(n,z)$ have $2^n$ distinct fixpoints $z$ for all $n$?

Let $f(z)$ be a given degree $2$ polynomial. Let $n$ be a positive integer. Let $f(1,z) = f(z)$ and $f(n,z)= f(1,f(n-1,z))$. How to decide if $f(n,z)$ has $2^n$ distinct fixpoints $z$ for all $n$ ?
2
votes
1answer
469 views

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if $1$ and $n$ also count as consecutive?

How many subsets does the set $\{1, 2, \dots , n\}$ have that contain no two consecutive integers if 1 and n also count as consecutive? It looks that the number of such subsets obeys the ...
4
votes
2answers
38 views

Solve $T(n) = 1 +\sum_{i=0}^{n-1}T(i)$

For the recurrence defined by $$T(n) = 1 +\sum_{i=0}^{n-1}T(i)$$ Apparently $T(n) = 2^n$ .. but I cannot see it. This recurrence pops up during analysis of the Rod Cutting Problem. I keep looking to ...
2
votes
1answer
60 views

How prove there exist postive integer $n$ such $x_{n}>y_{n}$

let two positive sequence $\begin{cases} x_{n+2}=x_{n}+x^2_{n+1}\\ y_{n+2}=y^2_{n}+y_{n+1} \end{cases}$ and $x_{1}>1,y_{1}>1,x_{2}>1,y_{2}>1$ show that: there exists $n$, such ...
7
votes
0answers
131 views

Mathematics of the Ice Bucket Challenge

I've been considering the mathematics of the now global ice bucket challenge. Simple model In the simplest incarnation, there is one original seed, who then nominates 3 others, each of which take ...
1
vote
1answer
58 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 ...
2
votes
1answer
32 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 ...
0
votes
2answers
113 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 ...
2
votes
0answers
30 views

Solution of partial difference equation

I want to find the explicit solution of the following difference equation $e_{i,j+1}=re_{i-1,j}+(1-2r)e_{i,j}+re_{i+1,j}+km_{i,j}$ where $r>0$, $k>0$ and $m_{i,j}$ are known and $e_{i,0}=0$. ...
5
votes
4answers
103 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
54 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 ...
10
votes
5answers
801 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 ...
2
votes
2answers
62 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 ...
0
votes
1answer
67 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
4answers
102 views

How do I prove convergence of the recursive sequence $c_n = c_{n-1} + \frac{0.01}{n}$?

I have this sequence: $c_n = c_{n-1} + \frac{0.01}{n}, \ \ c_1 = 0.01$ How do I prove the convergence of this, and what is the limit? Context I was trying to solve the problem of a snail crawling ...
0
votes
0answers
34 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
votes
2answers
177 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
1answer
63 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
1answer
25 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
97 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
120 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))$ ...
4
votes
1answer
95 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
54 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$ ...
-1
votes
1answer
91 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
26 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
1answer
213 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

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. ...
1
vote
2answers
53 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) = ...
2
votes
0answers
48 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
2answers
153 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} = ...
1
vote
1answer
65 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
69 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). ...
5
votes
3answers
782 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 ...
0
votes
1answer
175 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 ...
2
votes
2answers
44 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 ...
1
vote
0answers
70 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
1answer
38 views

$\Delta^kn^\alpha$ converges monotonically to zero when $\alpha<k$

I am trying to prove that the $k$-th finite difference of the series $n^\alpha$ converges to zero monotonically as $n\to\infty$ when $\alpha<k$. The differential analogue is ...
0
votes
0answers
27 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
1answer
102 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
47 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
28 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 ...
0
votes
2answers
45 views

Proof by induction that $f(1) + 2f(2) + 3f(3) + \cdots + n f(n) = f(n+1) - 1$, where $f(0) = 1$ and $f(K+1) = (K+1) f(K)$?

We've got the following function: $$f:N \rightarrow N$$ $$f(0) = 1$$ $$f(K+1) = (K+1)\times F(K)$$ How can I proof in induction the following: $$1\times f(1)+2\times f(2)+3\times f(3)+...+n\times ...
0
votes
2answers
41 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 ...
3
votes
5answers
113 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) ...
1
vote
0answers
31 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 = ...
5
votes
5answers
275 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 ...
8
votes
1answer
144 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 ...