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

learn more… | top users | synonyms (2)

0
votes
1answer
62 views

Find the order of elimination in Josephus Problem

Josephus Problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. People are standing in a circle waiting to be executed. Counting begins at the first ...
0
votes
0answers
30 views

Big-Oh, Big-Omega, Big-Theta determination

I am given a recurrence relation and told to solve it. Once we solve it we are supposed to determine whether it is in $O(f(n)), \Omega(f(n))$, or $\Theta(f(n))$. The relation is $t_n = 2nt_{n-1}$. ...
1
vote
5answers
96 views

Limit of the sequence defined by a recurrence

Given a recurrence formula for an arithmetic sequence, $$U_{n} = \frac{1}{2+U_{n-1}}$$ Show that$$\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{2+ ...}}}} = (SomeGivenValue)$$ How can we solve questions ...
0
votes
2answers
26 views

Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $$t_n = 2n~t_{n-1}$$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
2
votes
1answer
57 views

Recursive formula for word problem.

I'm having problems with this recursion problem: Ann wants to buy along several weeks one dressing item which can be of two kinds: small ones -- hats and scarfs, and big ones -- dresses, suits, gowns ...
0
votes
0answers
19 views

Solving a recurrence relation with 2 variables and 2 boundary conditions.

I am having some problem with solving a recurrence relation. Probably, the problem can be solved using a generating function, unfortunately I do not know how to deal with the boundaries of this ...
-1
votes
1answer
65 views

find number of strings

Find the number of strings consisting of only a and b which have P occurrence of aa Q ...
0
votes
2answers
50 views

Showing that the sequence $ x_n = \frac {1}{1 + x_{n-1}} $ is convergent

Sequence is recursively defined by $ x_0 = 1 $ I managed to show it is boundness by showing that $ 0 \lt x_n \lt 1 $ Now, when i try to show monotony of the sequence i got the problem because ...
1
vote
1answer
44 views

Recurrence relation with blocks

We have a path of size $N$ and $1\times1$ blocks of $4$ colors: yellow, red, blue and white. We need to fill the path with blocks but we cannot have $2$ blocks of the same color in a row (we can have $...
1
vote
1answer
43 views

Non linear recurrence relation?

for $ f: \mathbb N \rightarrow \mathbb N $, How do I solve $ f_n - f_{n+2} = f_{n+3} \times (f_{n+2} - f_{n+4})$ I tried the generating function but it only seems to work for linear relations. any ...
1
vote
3answers
39 views

How many such sequences exist?

Here is a sequence, $a_1, a_2, a_3, \ldots$ that satisfy the following property: $a_{n+2} = a_{n+1}+a_n$, where $a_m$ is a positive integer for any $m$, and it is known that $a_7 = 2015$. How many ...
1
vote
2answers
55 views

General solution of recurrence relation [closed]

I am supposed to solve for the general solution of $f(n+2)=2(f(n+2))^2 -f(n+2)f(n)-2012$. I tried the method of generating functions but I am stuck with the power $2$ on the RHS. any other methods or ...
0
votes
1answer
38 views

Can we solve this recurrence relation using recursion tree method

The recurrence relation is given as follows: $T(n) = 2T(\sqrt{n})+1$ $T(1) = 1$ I tried to solve it with recursion tree as follows: But to find the number of levels that may occur, I have to ...
0
votes
0answers
29 views

Solving two variable(dependent) recursion relation

I have the following recursion relation: $d(m,k)=d(m-1,k) + d(m-1,k-1) + ... + d(m-1,k-\min(k+1,m)+1); \hspace{2cm} m=1,2,3,...; k=0,1,2,...,\binom{m}{2}.$ with the following conditions $d(m,0) = 1,...
2
votes
0answers
14 views

Recurrence $x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$ solution

Let $x_k$ be the solution of the recurrence equation $$x_{k+1} = \sum_{i=1}^m \theta_i x_{k+1-i} + r_{k+1}$$ where $(r_k)$ is a general sequence. I'm trying to find a explicit solution for $(x_k)$ ...
2
votes
0answers
65 views

Closed form of $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $

Given the sequence $a_1 = 1$ and $a_2 = 1 $ with: $ a_n = 1 - \frac{a_{n-1} a_{n-2}}{4} $ Does there exist a closed form computing $a_n$ ? At the moment I have a problem getting a grip on the series:...
0
votes
1answer
41 views

How to solve the recurrence relation $T(n)=aT(n-1)+bn^c$ with $T(1)=1$

How to solve this recurrence relation? $ T(n)=aT(n-1)+bn^c \\T(1)=1,$ where a, b, c are constant. I want to solve it using generating function, but get stuck. Could anybody help me?
0
votes
0answers
14 views

Getting closed-form for $f(x) = \sum_{k=0}^n (f(x-c_1 k-c_2)+1)$

I have to get closed-form for the recursive function $f(x) = \sum_{k=0}^n (f(x-c_1 k-c_2)+1)$ Where $c_1,c_2 \in \mathbb{N}$ $f(x) = 0 \,\,$ for $\,\, 0 < x < c_2$ $f(x) = -1\,\,$ for $\,...
2
votes
0answers
23 views

Is $\sum \frac{n+1}{b_{n+1}}$ irrational, when $b_1=2$ and $b_{k+1}=2^kb_k(b_k-1)+1$, $k\geq 1$?

Let the sequences of positive integers $$a_n=n$$ when $n\geq 1$, and $$b_{n+1}=2^nb_n(b_n-1)+1$$ for $n\geq 1$ taking $b_1=2$. I've computed with previous sequences to assert that satisfy the ...
0
votes
0answers
34 views

Recurrence relation to find run time-complexity

int function(int n){ if (n<=1) return 1; else return (2*function(n/2)); } What is the recurrence relation $T(n)$ for running time, and why ? I believe is ...
0
votes
0answers
39 views

Growth of solutions of a second order recurrence equation with variable coefficients

Is it possible to determine whether the solutions of a second order difference equation with variable coefficients $$x_{n+2}+a_n x_{n+1}+b_n x_{n}=0$$ are growing with $n$ (for example exponentially) ...
1
vote
2answers
63 views

$f(6)=144$ and $f(n+3) = f(n+2)\{f(n+1)+f(n)\}$, Then $f(7) =$?

Given that $f(6)=144$ and $f(n+3) = f(n+2) \cdot\Big(f(n+1)+f(n)\Big)$ $[$For $n = 1,2,3,4]$ Then find the value of $f(7)$. The solution is not unique but all of them are positive integers. I can't ...
0
votes
1answer
24 views

how do I prove that for a recurrence relation of the form $a(2 n)=2^k a(n), a(n)=c n^{k}$ for some constant $c$?

if this is difficult, I am satisfied with an example for when $k=2$ in other words, how do I prove that for a recurrence relation of the form $a(2 n)=4 a(n), a(n)=c n^{2}$ for some constant c?
1
vote
1answer
32 views

Proving uniqueness of a steady state

I have a difference equation $$ p_t^{1-\alpha}=\alpha\sigma(y-p_t-\frac{(\sigma p_{t-1}^\alpha+b)p_t^{1-\alpha}}{\alpha\sigma}) $$ where $\alpha \in [0,1]$ and everything else is >0. I need to ...
1
vote
1answer
26 views

Inhomogeneous recurrence relation

I shall solve an inhomogeneous recurrence relation: $$x_n=2x_{n-1}+2^n,\quad x_0=2$$ My approach: The homogeneous part: $$x_n=2x_{n-1}\implies x_n-2x_{n-1}=0$$ With $x_n=x^n$ approach: $$x^n-2x^{n-1}...
0
votes
0answers
16 views

Bounds on the heights of the minimal polynomials of the algebraic coefficients of linear recurrence relations

Given a linear recurrence relation $$ a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k} $$ with characteristic polynomial $$ x^k-c_{k-1}x^{k-1}-c_{k-2}x^{k-2}-\cdots-c_0=(x-\beta_1)^{\alpha_1}(x-\beta_2)^{\...
1
vote
1answer
29 views

Simple difference equation

I have the following difference equation: $B(n) = \phi (B(n-1) )+ 1$, with a boundary that $B(0) = 0$. I can see that: $B(1) = 1$, $B(2) = 1+\phi$, $B(3) = \phi (1+\phi) + 1$. So the general ...
0
votes
2answers
36 views

Decreasing Recurrence Relation

Can someone solve this recurrence? $$ T(n) = 2T(n-1) + n^2 $$
1
vote
1answer
42 views

Error in the CLRS book for analyzing time complexity?

4.3-8 Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/2) + n^2$ is $\Theta(n^2)$. Wouldn't it be $\Theta(n^2 \log n)$?
1
vote
2answers
43 views

Divergence of a Recurrence Relation with the Divisor Function

Define the recurrence relation {$a_{n}$} as so: $$a_{n+1}=\tau(\sum _{ i=1 }^{ n }{ a_{ i } })$$ Where $\tau (n) =\sigma_0 (n)$, and $\sigma_k (n)$ is the divisor function. For example, if $a_1=6$...
0
votes
0answers
75 views

Upper bound on successive difference inequalities

I would like to know tight upper bounds of the following equations perhaps some might have telescopic sum which can result in very tight bound.In the following equations assume $B\geq a_i \geq 0$,$\...
1
vote
2answers
77 views

General solution for the series $a_n = \sqrt{(a_{n-1} \cdot a_{n-2})}$

Hey I'm searching a general solution for this recursive series: $a_n = \sqrt{(a_{n-1}\cdot a_{n-2})}$ $\forall n \geq 2$ $a_0 = 1$, $a_1 = 2$
1
vote
2answers
34 views

System of linear recurrences

During some computations I came up with the following system of linear recurrences: $$B_{n+2} = 3B_n + A_n \\ A_n = A_{n-1} + B_{n-1}$$ Here I am trying to find the solution for $B$ (hoping to get ...
1
vote
1answer
42 views

Making an infinite generating function a finite one

If we have some generating function $G(x)$ that generates terms indefinitely, is there a way to translate it to be a finite generating function? For example if I only want to generate the first $k$ ...
0
votes
0answers
17 views

How to solve for the constants of a non-linear equation?

I don't know the correct method to solve for the constants in equations like these (when I am trying to find the solution to a trial non-homogeneous recurrence): $$a\cdot n^2 + b\cdot n^3 + c\cdot n^...
0
votes
1answer
20 views

My nonhomogeneous recurrence trial solution fails

$$T_n = 6T_{n-1} - 13T_{n-2} + 12T_{n-3} - 4T_{n-4} + 5n^2 + 3n + 2 + 2^n + n2^n$$ The characteristic polynomial is $x^4 - 6x^3 + 13x^2 - 12x + 4 = 0$, or $(x-2)^2 (x-1)^2 = 0$. Therefore the ...
3
votes
1answer
37 views

Period of a Recurrence Relation

Let {$x_n$} be such a recurrence relations that obeys the following: For fixed naturals $a,b$, $x_ {n+1}$ is the least prime divisor of $ax_n+b$. Calculations showed that{$x_n$} appears to be ...
1
vote
1answer
15 views

A recurrence relation question - transforming

$a_{n+1}+{a_n}^2-2a_n=0$ I guess it is solved by transforming $a_n$ to some form of $b_n$. But I could not see the way. Would you explain the solution in details? Thanks.
1
vote
1answer
37 views

How to solve this non-homogeneous recurrence?

I've made a few threads recently asking how to solve non-homogeneous recurrences and I think I've gotten the hang of it, but now I want to try a complicated thing like this: $T(n) = 4T(n-1) + 2T(n-2) ...
3
votes
3answers
55 views

Finding the number of sequences with $0 \leq a_m \leq 3m$

Problem: Let $\alpha, \beta$ be non-negative numbers. Suppose the number of strictly increasing sequences $a_0, a_1, a_2 \cdots a_{2014}$ satisfying $0 \leq 3m$ is $2^{\alpha}(2\beta+1)$. Find $\...
0
votes
1answer
30 views

How to solve non-homogeneous recurrences?

I am trying to find a way to solve non-homogeneous recurrences by solving the homogeneous and non-homogeneous parts separately. I can use generating functions for the whole thing, but I want to learn ...
2
votes
4answers
110 views

Quick way to get closed form for this recurrence?

Is there supposed to be a fast way to compute recurrences like these? $T(1) = 1$ $T(n) = 2T(n - 1) + n$ The solution is $T(n) = 2^{n+1} - n - 2$. I can solve it with: Generating functions. ...
3
votes
2answers
106 views

Is it possible to solve such a system?

I have the following two equations: $$P_t = \frac{t-1}{t}P_{t-1} + \frac{1}{t}Q_{t-1}$$ $$Q_t = \frac{1}{t} + \frac{t-1}{t}Q_{t-1} - \frac{1}{t}P_{t-1}$$ with $P_0 = 0$ and $Q_0 = 0$. As time goes ...
0
votes
1answer
41 views

“Scaling” second-order linear recurrences.

Below is a screenshot from Sedgewick book with exact statement. I understand how to prove it, but what is the intuition behind this? I mean how the author found this fact? UPD I've come up with the ...
2
votes
1answer
61 views

How to derive sequence from generating function?

If you are solving a problem and you encounter a generating function that you haven't seen before, is there a way to derive its underlying sequence representation? For example I came across $\frac{1}{...
4
votes
2answers
40 views

Is my inductive proof correct?

Trying this again. Given $f(n) = 2f(n-1) + 1$ with $f(0) = 0$, I guess that $f(n) = 2^n-1$. Base case: $f(0) = 2^0 - 1 = 1 - 1 = 0$, true. Inductive step: Suppose $f(n) = 2^n-1$ for some $n \geq 0$....
1
vote
3answers
94 views

Now am I doing induction correctly?

Recursion: $L_n = L_{n-1} + n$ where $L_0 = 1$. We guess that solution is $L_n = \frac{n(n+1)}{2} + 1$. Base case: $L_0 = \frac{0(0+1)}{2} + 1 = 1$ is true. Inductive step: Assume $L_n = \frac{n(n+...
1
vote
0answers
53 views

How to solve even/odd divide-and-conquer problems?

I am looking into something called the Josephus problem, which seems to be popular, so I am sure there are lots of explanations online, but I want to do the work myself, but I do need a small push to ...
1
vote
1answer
33 views

Number of colorings under cyclic permutation.

Given $\lambda\vdash n$. How many ways to color $n$ beads of chaplet into $l$ colors, such that $\lambda_1$ of $1^{st}$ color, $\lambda_2$ of $2^{nd}$ color, etc. For, examples if $\lambda=(3,2)$, ...
0
votes
1answer
398 views

A function f(n) satisfies the recurrence f(n)=4f(n/2)+n for real numbers. Give an upper bound for f(n)?

A function f(n) satisfies the recurrence f(n)=4*f(n/2)+n for real numbers. Give an upper bound for f(n)? I get somewhere T(n) = Θ(n^2), is that correct?