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

learn more… | top users | synonyms (2)

6
votes
1answer
132 views

Limit related to the recursion $a_{n+1}=(1-n^{-1/4}a_n)a_n$

Let $0<a_{1}<1$, with $$a_{n+1}=a_{n}(1-n^{-\frac{1}{4}}a_{n})$$ Does there a real numbers $A$ which make the limit $$ ...
1
vote
0answers
20 views

Literature on functional difference equations

dear community. I'm looking for books/guides on functional difference equations. Can you recommend some? Below I try to explain what kind of equations I have in mind. As an example, one of the ...
29
votes
4answers
2k views

A stronger version of discrete “Liouville's theorem”

If a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}^{+} $ satisfies the following condition $$\forall x, y \in \mathbb{Z}, f(x,y) = \dfrac{f(x + 1, y)+f(x, y + 1) + f(x - 1, y) +f(x, ...
0
votes
2answers
1k views

converting a recursive formula into a non-recursive formula.

We found a recursive formula for the following problem: For any positive integer $n$, let $b(n)$ be the number of ways that you can write $n$ as a sum using only the numbers 1, 2, and 3 where the ...
0
votes
3answers
57 views

Recurrence relations for students of the third year of secondary school.

I am not able to solve this problem in order to find a explicit form for the recurrence relation (note: in the original text I can read "a with n" and "a with n-1", but I am not able to format here) ...
2
votes
2answers
101 views

How to solve the recurrence $T(n) = T(n-1) +\sqrt{n}$?

While solving the recurrence of the title I come to the series $$T(n) = \sqrt1 + \sqrt2 + \sqrt{3} + \cdots + \sqrt n.$$ Please somebody help me how to solve this.
7
votes
2answers
114 views

Is the sequence $x_{n+1} = \frac{x_n + \alpha}{x_n + 1}$ convergent?

Fix $\alpha > 1$, and consider the sequence $(x_n)_n \geq 0$ defined by $x_0 > \sqrt \alpha$ and $$x_{n+1} = \frac{x_n + \alpha}{x_n + 1}, n = 0, 1, 2, \dots$$ Does this sequence converge, ...
0
votes
1answer
37 views

Solve the recurrence relation

Assuming that $n$ is a power of $2$, solve the recurrence relation $$T(n)=2T\left(\frac{n}{2}\right)+2$$ Take $T(2)=1$ and $T(1)=0$. Also how can this be done with the master theorem, if possible?
0
votes
2answers
51 views

Find the values of $r_1, r_2, r_3$ in the recurrence relation $a_n = r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $

Consider the recurrence relation $a_n = > r_1 a_{n-1} + r_2 a_{n-2} + r_3 a_{n-3} $ for $n \ge 3$. The roots of the characteristic polynomial are $x = -1$ of multiplicity 2, $x= 3$ of ...
0
votes
1answer
40 views

How $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and So on?

I am currently reading 'concrete mathematics' of knuth. I don't know how $L_n = L_{n-1} + n $ become $L_{n-2} + (n-1) +n $ and finally $L_0+1+2...+(n-2)+(n-1)+n $ can you please tell me?
6
votes
1answer
172 views

Recurrence Relation

How do I solve: $k(k+1)a_{k}=2(\lambda k-1)a_{k-1}+(a-\lambda^2)a_{k-2}$ where $\lambda$ and $a$ are constants, and similar other recurrence relations?
0
votes
3answers
137 views

How to show that closed form of Fibonacci number is roots ratio difference of $n^{th}$ power of roots to difference of roots of $x^2 - x - 1=0$

1.5 The Fibonacci numbers $1,1,2,3,5,...$ are defined by the recursion formula $x_{n+1} = x_n + x_{n-1}$, with $x_1 = x_2 = 1$. Prove that $(x_n, x_{n+1}) = 1$ and that $x_{n} = \frac{a^n ...
1
vote
2answers
95 views

Counting numbers with the digit 5: How to express recurrence relation in closed form?

I figured out the algorithm for finding the count of numbers containing the digit 5 for any power of 10. What is the correct way to express y in this formula? $f(x) = 9y + (x/10)$ Where y is ...
0
votes
1answer
28 views

Recurrence relation task

Can someone explain me this: $T(n)=-T(n-1)+2\times T(n-2)+3 \times 2^n+n$ According to Wolfram Alpha the answer is: $$ T(n) = c_1(-2)^n + c_2 + \dfrac{1}{18}n(3n + 7) + 3 \times 2^n - ...
1
vote
2answers
33 views

Finding the inhomogeneous solution [duplicate]

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would I find the inhomogeneous solution for this since the homogenous solution is 0 given initial conditions?
0
votes
2answers
76 views

Calculating a percentage between two numbers

I have two numbers, a minimum value, and a maximum value. I also have a percent. This percent helps me find a value between the two numbers, the minimum value and the maximum value. I cannot figure ...
1
vote
1answer
69 views

Concerning a specific family of recursive sequences

There is a family of recursive sequences that I came up with: $$a_n=\text{sum of factors less than $a_{n-1}$ of } a_{n-1}, a_0\in\mathbb{N}$$ First question: Has it been studied before? Here are ...
1
vote
1answer
49 views

Solve the following recursive relation by using generating functions

$a_n - 9a_{n-1} + 26a_{n-2} - 24a_{n-3} = 0, n \ge 3, a_0 = 0, a_1 = 1,a_2 = 10$ I have tried solving it by the normal way, but I have no idea how to solve it by generating functions. Please give me ...
2
votes
1answer
102 views

Binary string block recurrence

Let $a_n$ be the total number of blocks for all $2^n$ binary strings with length $n$. Prove the following recurrence: \begin{equation*} a_n = 2a_{n-1} + \frac{2^{n}}{2} \end{equation*} For example ...
1
vote
1answer
26 views

Cardinality of a set with a recurrence relation.

Let $A = \left\{ f\in \mathbb{N}\rightarrow \mathbb{C} \mid \forall n\in \mathbb{N}. f(n+3) + 3f(n+1) = f(n+2)+f(n) \right\}$ What is $\left|A\right|$? Well, I tried to treat $f$ as a recurrence ...
0
votes
2answers
69 views

Complexity of $T(n) = 2T(n/2) + n$

How can I prove that $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \, \log{n})$ without master theorem , if $T(1)=\mathcal{O}(1)$? How can I continue from here? $T(n) = 2T(n/2) + n,$$T(n) = 4T(n/4) + ...
0
votes
2answers
259 views

find recursive solution $T(n)=2T(n/2)+n-1$

I want to solve this: $$T(n) = 2 T\left(\frac{n}{2}\right) + n - 1 $$ I try : \begin{align*} n &= 2^m \\ T(2^m) &= 2T(2^{m-1}) + 2^m -1 \\ 2 ^ m &= B \\ T(B) ...
2
votes
2answers
99 views

Calculate f(n+1)-f(n-1) based on f(n)???

Being: $$f(n) = \left(\frac{5+3\sqrt5}{10}\right)\cdot\left(\frac{1+\sqrt5}{2}\right)^n+\left(\frac{5-3\sqrt5}{10}\right)\cdot\left(\frac{1-\sqrt5}{2}\right)^n$$ Calculate: $$f(n+1)-f(n-1)\\ ...
-1
votes
2answers
50 views

Help solving recursive relations

$x_{n+2} = x_{n+1} + 20x_n + n^2 + 5^n \text{ with } x_0 = 0 \text{ and } x_1 = 0$ How would you solve this recursive relation? I have the homogenous solution, but am having issues with the ...
3
votes
2answers
63 views

Solving combinatorical problem using characteristic polynomial

How many $6$ length strings above $\left\{1,2,3,4\right\}$ are there such that $24$ and $42$ aren't allowed. The suitable recurrence relation for this problem is: $a_{n+2} = 2a_{n-1} + ...
3
votes
1answer
44 views

Uniqueness of solutions to linear recurrence relations

I understand that if I have a linear homogeneous recurrence relation of the form $q_n = c_1 q_{n-1} + c_2 q_{n-2} + \cdots + c_d q_{n-d}$, I can construct the characteristic polynomial $p(t) = t^d - ...
1
vote
4answers
130 views

How to solve a recursive equation

I have been given a task to solve the following recursive equation \begin{align*} a_1&=-2\\ a_2&= 12\\ a_n&= -4a_n{}_-{}_1-4a_n{}_-{}_2, \quad n \geq 3. \end{align*} Should I start by ...
1
vote
1answer
327 views

General solution of a system of linear differential equations with multiple generalized eigenvectors

I am looking for general solutions for the linear sODE's $$\textbf{x}'(t) = A\textbf{x}(t)$$ with $t \geq 0$ and $A \in \mathbb{R}^{n \times n}$ Let focus on just real eigenvalues and eigenvectors. ...
0
votes
3answers
77 views

Are Pell solutions “unique”??

Given the Pell equation $$X^2-2Y^2=1$$ and two solutions $(x_j,2uv)$ and $(x_k,2ac)$, with $uv=ac$ and $\gcd(u,v)=\gcd(a,c)=1$ and $u>v$ and $c>a$. Can one prove that $(u,v)=(c,a)$, and hence ...
3
votes
2answers
92 views

Find the limit of the sequence given by recurrence relation

Find the limit of the sequence given by recurrence relation $c_{n+1} = (1-\frac{1}{n})c_n + \beta_n $ where $ \beta_n $ is any sequence with the property $n^2\beta_n \to 0$ as $ n \to \infty$ I've ...
1
vote
4answers
76 views

A sequence was defined by a equation

The sequence was defined by the equations: $${a}_{1}=a\left(\in R \right),{a}_{n+1}=\frac{2{{a}_{n}}^{3}}{1+{{a}_{n}}^{4}},n\geq 1.$$ show that $\left(a \right)$The given sequence is convergent. ...
7
votes
1answer
308 views

How to prove this sequence of inequalities

The number $c_{g}(n)$ is defined by the recurrence \begin{equation} c_{g}(n) = c_{g}(n-1)+ (n-1)(n-2)c_{g-1}(n-2) , \end{equation} with $c_{0}(n)=1$ for any $n\geq 1$ and $c_{g}(n)=0$ if $n \leq 2g$. ...
2
votes
1answer
108 views

How can I make this recurrent equation non-recurrent?

I have a recurrent equation that defines a sequence $a_k$ from a sequence $b_k$: $$a_k = b_k - \sum^\infty_{i=k+1}a_i$$ How can I write this equation without mentioning $a_k$ on the right side?
1
vote
4answers
49 views

Help understanding Recursive algorithm question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$ For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ ...
0
votes
2answers
56 views

Is there a difference for discount per unit and discount per purchase total?

I can't find relevant tags for my question so I wonder if this is a good place to ask. I wanted to ask this a long time ago but keep forgetting. Let's suppose when shopping for 3 units of specific ...
1
vote
0answers
29 views

What [precisely] is special, algebraically, about fundamental Pell solutions?

I'm asking for a list of algebraic identities which "uniquely identify" (or nearly so) the fundamental solution (or those immediately around it) of a Pell equation. As a concrete [numerical] example, ...
1
vote
2answers
82 views

How do I find $\sum_{i=1}^n\frac{1}{x_i}$ where $x_i = x_{i-1} + \frac{1}{x_{i-1}}$

I have a recurrence: $x_n = x_{n-1} + \frac{1}{X_{n-1}}$. I need the value of n for which $x_n$ IS CLOSEST TO $2*x_0$, where $x_0$ is a positive integer. I tried the following: $x_1 = x_0 + ...
2
votes
1answer
69 views

Generating functions over $\mathbb{Z}$

Let $(a_n)_{n \in \mathbb{Z}}$ be a sequence such that both limits $\lim_{n \to \infty} a_n$ and $\lim_{n \to -\infty} a_n$ exists. Consider recursive relation $$ 2b_n - \frac{1}{2}(b_{n-1} + b_{n+1}) ...
0
votes
0answers
87 views

Recurrence Relation Challenges [duplicate]

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
1
vote
1answer
19 views

Sequence of integrals defined by recurrence

For a sequence of integrals defined as follows $F_0(x)=f(x)$ for some function $f(x)$, $F_n(x)=\int_0^x F_{n-1}(y)dy$ for all $n\geq1$, can we use change of variables to find a nice expression for ...
1
vote
0answers
146 views

Finite geometric sequence with a ratio greater than 1

I am trying to solve the recurrence relation: $ t(n)= 3T(n/2)+Cn$ (if $n>2$) $t(2)=C$ (otherwise) I know that there is the Master Theorem but I am trying to use the tree method. This ...
2
votes
1answer
42 views

Solving recurrence

Can anyone help me solving this recurrence? I don't see how I could use Master Theorem for this one and I couldn't find anything that would give me some idea how to do this. $$ T(n) = ...
2
votes
0answers
392 views

Linear multivariate recurrences with constant coefficients

In the theory of univariate linear recurrences with constant coefficients, there is a general method of solving initial value problems based on characteristic polynomials. I would like to ask, if any ...
0
votes
2answers
194 views

Solving a weird difference equation

I'm trying to find a way to solve the following difference equation, but I have exhausted all the resources at my disposal so now I come here for guidance. The equation is the following: $$x_1 = ...
5
votes
2answers
179 views

Let $x_{n+1} = x_n + 1/(x_1 + x_2 +\ldots + x_n)$ with $x_1 = 1$. Show that $x_n\sim\sqrt{2\log(n)}$.

As the title states we have a sequence defined by $$x_{n+1} = x_n + \dfrac{1}{x_1 + x_2 + \cdots + x_n}$$ with $x_1 = 1$. The first few terms are: $1, 2, \frac{7}{3}, \frac{121}{48} \cdots$ Any ...
-1
votes
1answer
80 views

Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
0
votes
1answer
59 views

Problem with making explicit formula from recursive formula

I'm having trouble turning this recursive formula into explicit one $a_0 = 0,\\a_{n+1} = a_n(1 - b_n) + b_n,$ where $(b_n)$ is given sequence of real numbers.
8
votes
0answers
118 views

Recurrence relations with multiple roots of auxiliary equation

Suppose we have a homogeneous linear recurrence relation of the form $$u_{n+r}+a_1u_{n+r-1}+\dots +a_ru_n=0$$ The auxiliary equation is then $$f(x)=x^r+a_1x^{r-1}+\dots +a_r=0$$ It is well known that ...
1
vote
1answer
26 views

recursive relation for putting signs in 2*n table

Consider we have a $2\times n$ table and we want to put a sign in some of the cells, and we don't put signs in both adjacent cells give a recursive phrase that shows that how many ways we can do that? ...