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

learn more… | top users | synonyms (2)

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
45 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
40 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
30 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
15 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
35 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
40 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
33 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
27 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
17 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
44 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
38 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
110 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
63 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
55 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
399 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?
3
votes
2answers
170 views

Give an upper bound for a function satisfying $f(n)=4f(n−1)+n$ [closed]

A function $f(n)$ satisfies the recurrence $f(n)= 4f(n−1)+n$ for real numbers. Give an upper bound for $f(n)$. Is the attached picture the correct answer?
1
vote
1answer
66 views

a nonlinear difference equation limit

let $$a_1=1, a_{n+1} = a_n + \frac{1}{a_n^2}$$, and it seems $$\lim_{n\to\infty} (a_n^3-3n-\log n) = \text{C}(constant) $$ I use computer program to verify that $$C = 1.13525585...$$,and expecting ...
1
vote
1answer
42 views

Is this true of all linear recurrences?

Is it true that any linear recurrence $f_n$ can be written as: $$f_n = \sum_{i=1}^{k} \alpha_i r_i^n$$ where $f_n$ is a linear recurrence of degree $k$ and $r_i$ represents a root of the ...
0
votes
1answer
35 views

Is my generating function correct so far for this recurrence?

Trying to teach myself generating functions. Recurrence: $a_n = 18a_{n-1} - 80a_{n-2}$ where $a_0 = 1$ and $a_1 = 9$. Attempt at using generating functions: $$G(x) = \sum_{n=0}^{\infty} a_nx^n \\ G(...
0
votes
3answers
32 views

Compressing two recurrences

I have two recurrences $a_n = 9a_{n-1} + b_{n-1}$ $b_n = 9b_{n-1} + a_{n-1}$ Is there a way to combine these two so it's only in terms of $a_n$? $a_1 = 9, b_1 = 1$, if this information is needed.
1
vote
0answers
19 views

Oscillations in a Discrete Dynamical System.

If you are familiar with SingingBanana on youtube, he posted the following question: There is a 10 digit number where the first digit tells me how many 0 there are in the number, the second digit ...
1
vote
0answers
40 views

How to correctly set up inductive proofs?

In practice, do you do some work on the inductive step and then reverse your steps? For example. Say you have this recurrence: $f(n+1) = 2f(n) + 1$ with $f(0) = 0$ This creates the sequence $0, 1, ...