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

learn more… | top users | synonyms (2)

2
votes
1answer
47 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
13 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
49 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
43 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
41 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
38 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
52 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
35 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
27 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) = ...
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 ...
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
38 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
28 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
19 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: ...
0
votes
0answers
15 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 $$ ...
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
34 views

Decreasing Recurrence Relation

Can someone solve this recurrence? $$ T(n) = 2T(n-1) + n^2 $$
1
vote
1answer
37 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 ...
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 ...
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
30 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 ...
0
votes
1answer
19 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
35 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
36 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
53 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
29 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
106 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
105 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
40 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
59 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 ...
4
votes
2answers
39 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 ...
1
vote
3answers
93 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 = ...
1
vote
0answers
44 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
32 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
389 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
169 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
65 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
34 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 \\ ...