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

learn more… | top users | synonyms (2)

1
vote
2answers
36 views

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$?

What's the time complexity of $T(n) =\sqrt{99nT(\sqrt {n})+100n}$ , I don't have an idea for solve the question. My attempt : $\frac{T(n)}{\sqrt {n}}^2 =99T(\sqrt {n})+100 $ and $\ s(k)= ...
0
votes
2answers
3k views

Recurrence telescoping $T(n) = T(n-1) + 1/n$ and $T(n) = T(n-1) + \log n$

I am trying to solve the following recurrence relations using telescoping. How would I go about doing it? $T(n) = T(n-1) + 1/n$ $T(n) = T(n-1) + \log n$ thanks
3
votes
1answer
1k views

Recurrence relation question

A country uses as currency coins with values of 1 peso, 2pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. a) Find a recurrence relation for ...
26
votes
2answers
521 views

How to calculate $\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$?

I need to calculate the sum $\displaystyle S=\sum_{n=1}^\infty\frac{(-1)^n}n H_n^2$, where $\displaystyle H_n=\sum\limits_{m=1}^n\frac1m$. Using a CAS I found that $S=\lim\limits_{k\to\infty}s_k$ ...
26
votes
1answer
565 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
0
votes
0answers
12 views

Simple closed functional form for summed recurrence relation

I'm struggling to obtain a simple closed form for a summed recurrence relation. I have an overall form $y=A\left(n-\sum_i^n\frac{e^{-x_i}}{B}\right)$ where $x_{i+1}=kx_i+m$ with $A,B,m >1$ and ...
-1
votes
0answers
26 views

Confluent hypergeometric function recurrence relation

How to prove the following contiguous relation for the Kummer function $M(a,b,z)$: $$(a−1+z)M(a,b,z)+(b−a)M(a−1,b,z)+(1−b)M(a,b−1,z)=0.$$
3
votes
5answers
60 views

How can I solve this recurrence relation: $a_n = 3a_{n-1} + \frac{4^n}{4}$?

How can I solve the following recurrence relation? $$a_n = 3a_{n-1} + \frac{4^n}{4}$$ I know that $a_n^{(h)} = 3a_{n-1}$ and that the characteristic equation is: $$r-3 = 0$$ and thus: $$a_n^{(h)} = ...
0
votes
0answers
39 views

Help fix this proof.

What is wrong with this proof? I followed the example of the answer to another one of my questions, here Define a general recurrence relation as $$f(x)^2=A(x)+B(x)f(x+n).$$ Substitute the root ...
10
votes
1answer
485 views

A polynomial sequence

I have a sequence of polynomials $Q_k(x, y)$, $k\geq 1$ defined recursively as follows: $Q_1=x$. There is a sequence of polynomials $p_j(y)$ of degree $j$ such that $Q_{2m}$ is of the form ...
1
vote
1answer
33 views

Asymptotic Estimates for a Strange Sequence

Let $a_0=1$. For each positive integer $i$, let $a_i=a_{i-1}+b_i$, where $b_i$ is the smallest element of the set $\{a_0,a_1,\ldots,a_{i-1}\}$ that is at least $i$. The sequence ...
0
votes
1answer
20 views

Closed solution to double recursion

I have a problem, where a subproblem is counting how many ways there are to interleave two words from disjoint alphabets while keeping the relative order of the letters within each word. For example, ...
0
votes
2answers
24 views

Recurrence Relation solution

How do I solve the following recurrence relation and what kind is it ? $ a_n = a_{n-1} + c $ ? where c is constant Can this relation be considered non-homogenous as $ F(n) = c.n^0 $ ?
0
votes
2answers
16 views

$T(n) = 3T(n/3) + c$ using substitution, geometric series

so I have to find the asymptotic complexity of $T(n) = 3Tn(n/3) + c$ using either the substitution method, a recursion tree or induction. I used the Master Theorem to find an answer, but can't use ...
1
vote
3answers
116 views

Solving the recurrence relation $T(n) = 2T(n^\frac{1}{2}) + c$

I've been trying to do this for hours. I just don't know how. I'm familiar with recurrence relations in the form of $T(\frac{n}{2})$, but what do you need to do to solve $T(n^\frac{1}{2})$? I've ...
0
votes
1answer
30 views

Nonconstant solutions of discrete predator and prey model and Perron-Frobenius

Consider the discrete dynamical system given by $x_{n+1} = A x_n$, where $A = \begin {pmatrix} a & -b\\c &d\end {pmatrix}$ and $x_n = \begin {pmatrix} u_n\\v_n\end {pmatrix}$. Are there ...
-1
votes
1answer
41 views

Recurrence relation solving [closed]

The recurrence relation given is $$ T(n) = 2T(\lceil\sqrt{n}\rceil) + 1, \text{ with }T(1) = 1 $$ I want an explanation about the order of the solution of this recurrence relation
0
votes
0answers
43 views

Finding the explicit formula of linear homogeneous recurrence relations.

I'm not sure if this equation is a linear homogeneous recurrence relation because I didn't learn math in english. what is the explicit formula for $f$? $f(x) = f(x-2)-{n^{x-1}\over NW-1} ...
3
votes
1answer
469 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
2
votes
1answer
105 views

Recurrence relation / recursive formula / closed formula for partition numbers (1,2,3,5,7,11,15,22,30,42,…)

I have already read this: Number partition - prove recursive formula But the formula from the above link requires a parameter k which is the required number of ...
1
vote
3answers
204 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...
0
votes
1answer
20 views

Substitution method for solving recurrences

I see this in CLRS: We can use the substitution method to establish either upper or lower bounds on a recurrence. As an example, let us determine an upper bound on the recurrence ...
1
vote
2answers
36 views

Can this recurrence relation be solved with generating functions?

I have this recurrence relation, $$a_{n+1}=\frac{n+2}{n}a_n$$ with $a_1=1$. I've already solved this using a substitution approach by letting $a_n=\dfrac{(n+1)!}{(n-1)!}b_n$. This means ...
2
votes
2answers
67 views

Understanding Generating Function

I have been looking at This Problem and Answer about generating functions. The problem asked for the generating function of: $$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1$$ I understand how Ron Gordon ...
4
votes
2answers
133 views

Convergence of sequence: $f(n+1) = f(n) + \frac{f(n)^2}{n(n+1)}$

I am trying to work out a problem on some old analysis qual exam, and managed to reduce it to this question, but I can't seem to figure out this final step: Consider the sequence defined by the ...
4
votes
2answers
60 views

Choose initial values such that sequence always has integer values

We are given a recurrence relation defined by $$x_{n+2}=\frac{x_{n+1}x_n}{2x_n-x_{n+1}}.$$ Place necessary and sufficient values on $x_0$ and $x_1$ such that $x_n$ is an integer for all positive ...
1
vote
3answers
55 views

Ordered Sum of Odd Numbers

EDIT: The vectors can be any length. That is $k$ is not fixed. For a given natural number $n$, let $S_1(n)$ be the number of vectors $(a_1, a_2, \ldots, a_k)$ such that $$a_1 + a_2 + \cdots + a_k = ...
1
vote
1answer
34 views

How to come up with this recurrence relation for putting p rooks in a m×n chessboard?

I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position. (Two rooks attack each other if they are in the same row or same column) How many ways ...
1
vote
3answers
484 views

Number of subsets of $\{1,2, \ldots, n\}$ containing no three consecutive integers: recurrence equation?

I'm thinking about the problem below. I know that I have to find a polynomial formula for that first, and then from that polynomial formula I can find the recurrence relation. I actually attempted ...
4
votes
3answers
251 views

Mathematical Induction proof for a cubic equation.

If $ x^3 = x +1$, prove by induction that $ x^{3n} = a_{n}x + b_n + \frac {c_n}{x}$, where $a_1=1, b_1=1, c_1=0$ and $a_n = a_{n-1} + b_{n-1}, b_n = a_{n-1} + b_{n-1} + c_{n-1}, c_n = a_{n-1} + ...
4
votes
1answer
94 views

Infinitely nested radical problem?

I became interested in this nested radical from another question and thought I would have a go at trying to come up with a formula for it. It is $$G(0)=\sqrt{1+\sqrt{2+\sqrt{4+\sqrt{8+\cdots}}}}.$$ ...
19
votes
5answers
1k views

Closed form for the sequence defined by $a_0=1$ and $a_{n+1} = a_n + a_n^{-1}$

Today, we had a math class, where we had to show, that $a_{100} > 14$ for $$a_0 = 1;\qquad a_{n+1} = a_n + a_n^{-1}$$ Apart from this task, I asked myself: Is there a closed form for this ...
0
votes
1answer
25 views

Solve a recurrence in terms of n

I'm trying to determine the order of growth of a recursive algorithm but I only got a recurrence. Please somebody explain me how to solve the following recurrence with $k = 2$: ...
3
votes
1answer
33 views

Solving recurrence equation with floor and ceil functions

I have a recurrence equation that would be very easy to solve (without ceil and floor functions) but I can't solve them exactly including floor and ceil. \begin{align} k (1) &= 0\\ k(n) &= ...
0
votes
1answer
64 views

Recurrence relation: $c_{k+1}=c_k+\frac{1}{(k+1)!}$

I have no idea how to proceed solving a recurrence relation like this. I know that the terms approach $e$ but beyond that I have no idea. The relation is$$c_{k+1}=c_k+\frac{1}{(k+1)!} \ \ ; \ c_0=1$$ ...
1
vote
0answers
24 views

asymptotics of Involutions recurrence relation

Consider the following recurrence relation where $t(n)$ is the number of involutions on $\{1,...,n\}$ \begin{equation} (n+1)t(n)+t(n+1)-t(n+2)=0 \end{equation} When $n \rightarrow \infty$, Wimp and ...
2
votes
0answers
46 views

Recurrence equation approximation

I have the following recurrence relation, $$x_{i+1}=a\cdot x_i^{\frac{2-2\alpha}{3}}+x_i,$$ where $a>0, \alpha>0$, and $x_0>0$. My goal is to get an approximate the expression for $x_i$. I ...
4
votes
2answers
206 views

Finding a recurrence for a sum

I am trying to implement the following sum using a programming language: $$\sum_{i=1}^N a^i i^r$$ where $N$, $a$ and $r$ are integers. The problem is, I cannot find a suitable way to do this. ...
0
votes
1answer
35 views

Linear Recurrence Using matrix exponentiation

Matrix Exponentiation can be used to solve Linear Recurrence . I know how to solve linear recurrences like : $f(n) = f(n-k_1) + f(n-k_2) + ... +\ constant$ But i couldn't find any information on how ...
2
votes
1answer
37 views

FSR function of the component-wise product, sum, of two LFSR sequences

Let $T_1$, $T_2$ be two $m$-sequences over $\mathbb{F}_q$ of length $q^n-1$, say $T_1 = (\text{Tr}_{q^n | q}(\alpha^i))_{i \geq 0}$, $T_2 = (\text{Tr}_{q^n | q}(\beta^i))_{i \geq 0}$, for some ...
0
votes
1answer
56 views

Are there ways to separate the Fibonacci sequence? [closed]

I am wondering if there are ways to separate the set of Fibonacci numbers, $F$, into sets $A$ and $B$ such that $$A + B = \{a+b:a\in A,\,b\in B\}=F$$ and such that $A$ and $B$ do not follow the ...
2
votes
0answers
84 views

Validity of approximating a difference equation with a differential equation

Consider the following two equations: $$ \begin{cases} A_k(n+1)-A_k(n)=\beta \displaystyle \frac{ A_{k-1}(n)- A_k(n)}{\alpha+ n} + \delta_{k, \beta} \\ \\ \displaystyle ...
1
vote
2answers
37 views

Closed form for multiplicative recurrence relation

In this StackOverflow question, I found an interesting recurrence relation: $$f(n) = \begin{cases} 1 & n \leq 2 \\ nf(n-1) + (n-1)f(n-2) & \text{otherwise.}\end{cases}$$ I plugged it into ...
5
votes
1answer
140 views

How can I show that the sequence $x_n^2$ is bounded?

Two real sequences $(x_n)$ and $(y_n)$ are defined by $$x_{n+1}=x_n-(x_ny_n+x_{n+1}y_{n+1}-2)(y_n+y_{n+1})$$ $$y_{n+1}=y_n-(x_ny_n+x_{n+1}y_{n+1}-2)(x_n+x_{n+1})$$ with initial conditions $x_0=1$ and ...
2
votes
1answer
59 views

Find product limit of this recursively-defined sequence?

Problem: if $a_1=3$, $a_n=2a_{n-1}^2-1$, $n\ge2$, find the limit of this expression: $$\lim\limits_{n \to ∞} \prod\limits_{k=1}^{n-1} (1+\frac {1}{a_k})$$ The original problem asks to find ...
1
vote
0answers
33 views

Special Non-linear recurrence

Problem I have a non-linear recurrence relation given by $$ a_n = a_{n-1}+a_{n-2}+a_{n-3} - \sqrt{a_{n-1}.a_{n-2}+a_{n-2}.a_{n-3}+a_{n-3}.a_{n-1}} $$ Given $ a_1, a_2 $ and $ a_3 $,I have to find ...
4
votes
1answer
49 views

Recurrence relation in terms of another sequence

How do I solve a recurrence of the form $$nd^{n-1}a_n+a_{n+1}d^{n+1}=b_n$$ for $a_n$, where $b_n$ is another (known) sequence and $d$ is a constant? My only idea was to use a generating function and ...
2
votes
0answers
78 views

Number of unordered factorizations into $k$ distinct parts

Let $H_d(n)$ denote the number of distinct ordered factorizations of $n$ and $H_d(n,k)$ the number of ordered factorizations of $n$ into $k$ distinct parts. We have the following recurrence: ...
1
vote
2answers
39 views

The derivative of a recurrence relation of functions

I am unsure of how to take the derivative of a recurrence relation of functions. For example consider the following recurrence relation: \begin{equation} \left\{ \begin{array}{cl} f_n(x) &= ...
1
vote
2answers
66 views

Finding a Solution to a Equation that Ends up as a Weird Repeating Series

I need to find the solution to this equation that ends up in a weird repeating series. The equation in question is: $$ \ln(y)=\frac{K}{\alpha}+\frac {x^{2}}{2\alpha\sigma}+\frac{\ln(\ln(y))}{2\alpha} ...