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

learn more… | top users | synonyms (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
34 views

Decreasing Recurrence Relation

Can someone solve this recurrence? $$ T(n) = 2T(n-1) + n^2 $$
1
vote
1answer
40 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
33 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
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
36 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
54 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
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
60 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
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 ...
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 = ...
1
vote
0answers
48 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
393 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
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
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
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
39 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
32 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
28 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
33 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
104 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
46 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
42 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
55 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
53 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
44 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$} ...
2
votes
0answers
47 views

Asymptotics of recursion

suppose we have the following two sequences $$\alpha_k = (k-1)\left(1-\frac {1}{1+(k+1)l}\right) \quad , k \geq 2$$ $$\beta_k = (k-1)\left(1+\frac {1}{1+(k-1)l}\right) \quad , k \geq 2$$ where ...
2
votes
2answers
49 views

Recurrence relation - How To Give a Combinatorial Proof

Problem: Consider the set $S$ of all “ternary strings” (strings in the ‘alphabet’ {$0$, $1$, $2$}), such that a $0$ never is directly followed by a $1$ or a $2$. (Thus, e. g. the strings $12100$ and ...
1
vote
0answers
40 views

Proof that common differences imply a polynomial-generated sequence

I have long been familiar with the method of common differences for finding the equation of a sequence: you subtract consecutive terms going down level by level, until you get a constant difference at ...
0
votes
2answers
95 views

Perplexing integral

First and foremost, is it possible to get the integral you are trying to solve as the solution? I just got the same integral twice. I have also tried MATLAB but it gives the same result. Below is the ...
0
votes
0answers
37 views

A particular recursion

Given $s_0=2^r>0$ let $s_i=\frac{s_{i-1}}{2^{\log^c{r_{i-1}}}}$ where $c\geq1$ and $r_{i+1}=\log_2(s_{i+1})=r_i-(\log_2(r_{i}))^c\leq r_{i}$. What is the value of smallest $i$ at which $s_i<1$ ...
3
votes
1answer
71 views

Convergence of sequence of ratio of consecutive terms.

I would like to prove that the following sequence of ratios $(x_n)$ where $x_n = c_n/c_{n-1}$ converges to a finite limit $L$: $$\lim_{n\to\infty} x_n = \lim_{n\to\infty}\frac{c_n}{c_{n-1}} = L$$ ...
8
votes
0answers
76 views

Find the recurrence formula for $\int \frac{dx} {(1+\sin x)^n}$

$$\int \frac{dx} {(1+\sin x)^n}$$ I know that I should use the following step: $$\int\frac{\sin^2(x)\, dx}{(1+\sin x)^n} +\int\frac{\cos^2(x)\, dx} {(1+\sin x)^n} $$ but here I get stuck. I do not ...
0
votes
0answers
56 views

A(n) = A(n-2) - nA(n-1) general formula?

I was working on a problem involving a continuous fractions. To solve the problem i would need to find a general formula for this sequence as a function of the two initial values A(1) and A(2). ...
0
votes
1answer
72 views

How do I find a recurrence relation?

Let n1, n2, . . . , n100 be a sequence of integers. Initially, n1 = 1, n2 = −1 and all the other numbers are 0. After every second, we replace the kth term of the sequence with the sum of the kth and ...
0
votes
1answer
52 views

Find $u_3$ of recurrence relation $u_{n+1} = 0.2u_n + 9$ when only $u_5$ is known [closed]

A sequence is defined by the recurrence relation $u_{n+1} = 0.2u_n + 9$, ${u_5 = 11}$. What is the value of ${u_3}$? I have not encountered a problem like this when only one value for n is ...