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

learn more… | top users | synonyms (2)

1
vote
2answers
62 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
12 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
14 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 $$ ...
0
votes
0answers
29 views

Time complexity of $T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$

$$ T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$$ $$ T(0) = 1 , T(1) = 2 $$ This is my $T(n)$, and I need to find its time complexity. I know the answer is $T(n) = \theta (n2^n)$, but I have a problem with ...
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
33 views

Decreasing Recurrence Relation

Can someone solve this recurrence? $$ T(n) = 2T(n-1) + n^2 $$
1
vote
1answer
28 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
35 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
70 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
70 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
28 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
40 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
15 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
18 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 ...
-5
votes
0answers
50 views

How to calculate the limit of this sequence

Let ${x}_n$ a convergent sequence of real numbers . If $x_1 > \pi+\sqrt{2}$ and $ x_n = \pi+\sqrt{x_n -\pi} $ for $ n>1$, then what is the limit of the sequence?
3
votes
1answer
32 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
32 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) ...
0
votes
1answer
20 views

Convergence of the Ratio of Consecutive Terms of Positive Recurrence Sequences (Reference Request)

I would like to locate a source that shows (or gets pretty close to) the following. Let $S$ be a positive (integer) recurrence sequence $S_n=S_{n-1}+S_{n-k}$ for some $k>1$. Then, ...
3
votes
3answers
48 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
24 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 ...
1
vote
1answer
17 views

Solving an arbitrary linear recurrence relation

How can I solve an arbitrary linear recurrence relation like this: $$ A a_{n+2} + B a_{n+1} + C a_n = D $$ Is there a method that I can use to deal with arbitrary LRRs?
2
votes
5answers
87 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
104 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 ...
-1
votes
0answers
25 views

Single element of nth power of a Matrix

I was recently solving a computational problem which had a recursive structure. With some help from the internet and a paper I found, I used mathematica to find a transformation matrix for the ...
0
votes
1answer
22 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
57 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
90 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
27 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
29 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
160 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
128 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
60 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
40 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 \\ ...
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
17 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
37 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, ...
0
votes
3answers
31 views

Not Deducing a Closed Form for Recurrence Relation Correctly

Here is a recurrence relation $$a_1 = 2$$ $$a_{n+1} = \frac{1}{2}(a_n + 6)$$ where $n \in \mathbb{N}$. For hiccups and giggles, I wanted to determine a closed form for the recurrence relation. ...
1
vote
0answers
23 views

General periodic recurrences

I was blown away when I read in Concrete Math that the recurrence $$Q_0 = \alpha$$ $$Q_1 = \beta$$ $$Q_n = \frac{Q_{n-1} + 1}{Q_{n-2}}$$ is periodic (period 5). Is there a general method to determine ...
0
votes
0answers
26 views

lotto draws- calculate the number of successes in full growth

In my country we have a special lottery There are 45 numbers and you can choose as many as you like in order to get right the 5 winning numbers. For example you can choose 10 out of the 45 numbers ...
1
vote
1answer
94 views

An optimal sequence of length 13

I'm looking for an optimal (or much better than I have now) increasing sequence $t_1, t_2, .., t_{13}: t_i \in N, 0 \le t_i<t_{i+1}$ where $3t_{12} + 4t_{13}$ is minimized, subject to the ...
1
vote
1answer
44 views

Why can't this be done with Master Theorem

Apparently recurrences like this cannot be solved with the Master Theorem: $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$ Because $n^{\log_b(a)} = n^1$ is not a polynomial multiple of $f(n) ...
1
vote
2answers
41 views

How to analyze the time complexity $\Theta$ of this recurrence

I am trying to understand how to show that $$T(n) = T(n/2) + T(n/4) + n^2$$ is $\Theta(n^2)$ by using a recursion tree. I tried substitution at first but it got real messy real fast. This is ...
0
votes
0answers
28 views

Is exponential decay a moving average filter?

I learned that a moving average filter is an FIR filter that gives the average of $N$ previous inputs, like this: $y_n = \sum_{i=0}^{N-1}\frac{x_{n-i}}{N}$ As a simple extension, it might be some ...
2
votes
2answers
45 views

number of ternary trees: finding a recurrent relationship

If $t_n$ is the number of ternary trees with n nodes, with $t_0=0$, what would be the convenient manner for finding a recurrent relationship for $t_n$? It is given that $t_1=1, t_2=3, t_3=12$. A ...
0
votes
1answer
37 views

Closed form solution for recurrence relation with 2 variables

Please help me in finding the closed form solution for the recurrence relation : \begin{align*} f(n, d) &= 2 \sum\limits_{i=1}^{n-1} f(i, d-1) + f(n, d-1) \\ & \text{for $n > 1, d > 1$} ...