Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [recurrence-relations]

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

0
votes
0answers
20 views

Trace of ordinary differential operator

Let $n$ be an odd natural number, $a_k(x)$ functions defined on an interval and $$Df(x)=\frac{d}{dx}(a_1(x)\frac{d}{dx}(a_2(x)\dots\frac{d}{dx}(a_{n}(x)\frac{d}{dx}f(x))\dots)$$ be an ordinary ...
0
votes
0answers
22 views

Explain recurrence and Dynamic Programming methods

Well during competitive programming, Dynamic Programming and Recursion is one of the most favorite topics. It kind of draws the line between an average and a good coder. Now my question is, is there ...
0
votes
0answers
8 views

Relationship between the initial value of the recurrecne relation to the limit

Let $a_1$ be the first term of of sequence. Now define $$a_{n+1}=R(a_n)$$ where R is any recurrence relation. Assuming that $\lim_{n\rightarrow }a_n$ exists , I am looking for a relationship between ...
0
votes
3answers
42 views

Recurrence relation: $T(n) = \sum_{k = 0}^{n-1} \binom{n-1}{k}T(k)T(n-k-1)$ [on hold]

Solve the recurrence relation $$T(n) = \sum_{k = 0}^{n-1} \binom{n-1}{k}T(k)T(n-k-1),$$ where $T(0) = T(1) = 1$ .
-2
votes
0answers
33 views

Solving the recurrence inequality $ f(n) \leq \frac{1}{1- \sum_{i=0}^{n-1} f(i)}$ [on hold]

How to solve the recurrence inequality $$ f(n) \leq \frac{1}{1- \sum_{i=0}^{n-1} f(i)}$$
5
votes
0answers
42 views

Assume $x_n>0$,$x_n+\dfrac{4}{x_{n+1}^2}<3.$ Prove $\lim\limits_{n \to \infty}x_n$ exists and evaluate it.

My Solution Notice that $$x_n+\dfrac{4}{x_{n+1}^2}<3=3\sqrt[3]{\frac{x_n}{2}\cdot\frac{x_n}{2}\cdot\frac{4}{x_n^2}}\leq \frac{x_n}{2}+\frac{x_n}{2}+\frac{4}{x_n^2}=x_n+\frac{4}{x_n^2}.$$ This ...
-1
votes
1answer
36 views

How to find $\Delta a_n$? - recurrence relation [on hold]

Sequences fulfills recurrence $a_{n+2}=a_{n+1}-2a_n$ and $ 2a_{n+2}=3a_{n+1}+2a_n$. Find $\Delta a_n$ if $a_0=1$
0
votes
1answer
96 views

closed form of f(n,k) = f(n-1,k-1) + f(n-1,k) + f(n-2,k-1) [on hold]

I am stuck at solving linear recurrence relation of 2 variables : f(n,k) = f(n-1,k-1) + f(n-1,k) + f(n-2,k-1) what would be closed form for f(n,k)? Base ...
0
votes
1answer
34 views

What does it mean to solve recurrence relation?

$$f(n)=3f(n-1)-f(n-2)-3f(n-3)+2f(n-4)-4$$ $$f(0)=0,f(1)=1,f(2)=2,f(3)=3$$ Given some recurrence relation with these starting conditions. What does it mean to solve it? I don't need a solution for the ...
0
votes
1answer
19 views

Using the diagonalisation of a matrix to solve a recurrence relation

I have a problem I've been having quite some trouble to solve. Here it is. We are given that $y_{t+1} = -\frac{3}{2}y_{t}+y_{t-1}$ and $x_t = y_{t+1}-y_t$ a) Find a matrix $A$ s.t $$ \left(\begin{...
0
votes
0answers
27 views

Solve a 2 variable recurrence relation with 3 terms

$f(n,k) = f(n-1,k) + f(n-1,k-1) + f(n-2,k-1)$ $f(n,1) = 2n$ $f(1,k) = 2$ if $k = 1$ $f(1,k) = 0$ if $k\geq2$ $f(2,k) = 4$ if $k = 1$ $f(2,k) = 2$ if $k = 2$ $f(2,k) = 0$ if $k\geq3$ How to ...
0
votes
0answers
11 views

Find complexity of recurrence relation

I'm trying to find the complexity of this recurrence relation: $$T(1)=1 \\ T(N)=c(\lg N) + T(N/2)$$ My attempt at solution: Let $N=2^k$. Then: $$T(N)=T(2^k)=c \lg(2^k) + T(2^{k-1})=c \lg(2^k)+c \...
0
votes
1answer
42 views

What is the relation between the solution $y_{n}$ and the solution $x_{k}$ of the same recurrence equation

I have the following problem which I cannot find a solution: Let us consider a recurrence relation of the form $$x_{k+1}=f(x_{k})$$ The function is real valued, continuous and strictely increasing ...
1
vote
0answers
27 views

Recurrence Relations with non-constant coefficients

Consider the following recurrence relations: The equations for x and y are similar and connected to each other at $x_1, y_1, x_n$ and $y_n$. $x_1(t) = \frac{1}{2\sqrt{x_1(t-1)^2 + y(t-1)^2}} x_1(t-1) ...
1
vote
1answer
30 views

How to find the closed form solution for the multivariate recurrence?

Recurrence relation: f(n,k) = f(n-1,k) + f(n-1,k-1) + f(n-2,k-1) Initial conditions: ...
0
votes
0answers
16 views

How to get the depth of a recursion tree (help with logs)?

I'm reading this example from this site https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html, and trying to understand the example: $T(n) = T(n/3) + T(2n/3) + n$. Mostly I'...
-3
votes
0answers
37 views

Solve the recurrence relation $T(n) = (n-1) T(n-1)$

How do I resolve the following recurrence relation? $T(n) = (n-1) T(n-1),$ $T(1) = 1.$ My reasoning: $T(n) = T(n-1-k)(n-1)(n-2)(n-3)\cdots(n-k)$ $k = n$ $\leftarrow$ yields the ...
3
votes
1answer
107 views

Solve recurrence relation!

I was working with this recurrence relation : $$\begin{cases}A(n,k) = A(n-1, k-1)+A(n-2, k-1)+A(n-1, k)\\ A(n, 0) = 1\\ A(n, 1) = 2n \end{cases}$$ Generating function : $(1+x)/(1-x-x*y-x^2*y)$ ...
1
vote
1answer
22 views

Finding the geometric sum of this recurrence

I'm having trouble with evaluating geometric sequences that look like this: $Cn\sum_{i=0}^{\log_3n} (5/3)^i$ where $n$ is the number of operations, and $Cn$ just represents $n$ times some constant $...
0
votes
0answers
13 views

How to solve this linear non-homogeneous recurrence relation with constant coefficients?

I need help in solving this recurrence relation. $F(n) = 2F(n-1) + 3F(n-2) + n*7^n$ I truly have no idea of where to start with because of this term $n*7^n$
0
votes
1answer
84 views

Solving two dimensional recurrence relations

I want to know how to approach this two dimensional recurrence relation and how can a generating function be generated for this recurrence. $$F(N,K) = F(N-1,K) + F(N-1,K-1) + F(N-2,K-1)\text{ with }N&...
3
votes
0answers
33 views
+50

Solving 2-dimensional recurrence matrix of homogenous polynomials

In $2012$, Rajkumar presented an interesting simplification of Apéry's theorem, i.e., that $\zeta(3)$ is irrational, where $\zeta$ denotes the Riemann zeta function. I am trying to understand his ...
0
votes
1answer
26 views

Recurrence formula for division of a sphere by n great circles

Find the recurrence relation satisfied by $R_n$, where $R_n$ is the number of regions into which the surface of a sphere is divided by n great circles (which are the intersections of the sphere and ...
0
votes
0answers
59 views

Upper bound of a sequence for all n

Let $r_n$ is a non-increasing sequence such that $ 1 \leq r_n \leq 1 + \theta_1^2 + \theta_2^2$ and $r_n \rightarrow 1$ as $n \rightarrow \infty$. Further we know that $|\theta_2| < 1$ and $|\...
-2
votes
1answer
29 views

Recursive Sequence to Explicit Sequence [on hold]

i try to prove this, Let $a_1=-5$, $a_2=-26$ and $\forall n\geq 2$, $$a_{n+1}=5a_n - 6a_{n-1} + 5 \cdot 2^{n-1}.$$ Then, $$a_n= 3 \cdot 2^n - 2\cdot 3^n - 5n \cdot 2^{n-1}.$$ Maybe, telescopic ...
0
votes
1answer
21 views

Solving coupled recurrence equations with non-constant coefficients

I've been looking at this way too long on this problem now, and perhaps I'm just not seeing it clear but I can't figure out how solve the coupled recurrence equations $a_n, b_n$ with non-constant ...
0
votes
1answer
19 views

Find a recurrence relation for the number of ternary strings that do not contain consecutive symbols that are the same.

I tried to solve this question by subtracting the number of strings that contain consecutive symbols that are same from the total number of symbols possible of length n. Let bn denote the number of ...
0
votes
0answers
61 views

Solving recurrence equation in two variables

I have a recurrence, $$F(n, m) = F(n-1, m) + F(n, m-1) + F(n-1,m-1) $$ $$F(n,1) = 0$$ $$F(1,n) = 2*(n-1)$$ I would like to compute $F(N,M)$ in terms of $N$ and $M$. The system is defined for $1 \...
0
votes
0answers
36 views

Recurrence relationship $F(n+2)-2F(n+1)-8F(n)=0$

$$F(n+2)-2F(n+1)-8F(n)=0$$ Our solution is trigonometric algebraic $$ 2^n(2^n-\cos(\pi n)) $$ My question is as fallow, can we find solution to this recurrence relation that has solution $$ F^m(n)=F(n)...
-2
votes
1answer
61 views

$a_{n+1}=a_{n}^{2}-2 $ [closed]

I know $$ a_{n+1}=a_{n}^{2}-2 $$ has a closed form. If a_1 is given in complex number and solve this recurrence relation . How solve this without using induction.
0
votes
1answer
38 views

Use recurrence relations to find strings with odd numbers of 0's

You are given all n-digit strings in which each digit is 0, 1, or 2. Using the product rule and/or the sum rule, count the number of these strings that have an odd number of 0’s when n (the number of ...
0
votes
0answers
11 views

Non homogeneous recurrence relation with min functions

I hope all is well. I have been trying to work out this pattern. but I can't get my head around simplifying this into a formula. $$ n_{r + 1} = g \cdot \min\left(ox^{r}, wq^{r}\right) + P \cdot \min\...
0
votes
1answer
40 views

linear recurrence relation with inhomogeneous trigonometric term

Find the explicit sequence that satisfy: $$ x_{n+2}-3x_{n+1}+2x_n= \cos^2(\frac{\pi}{2}n)\sin(\frac{\pi}{6}n)$$ and the initial condition $$x_0=x_1=0$$ My first attempt was to compute some term and ...
0
votes
0answers
39 views

Multivariate Recurrence Relation

$$A(n, k) = 2 \cdot \sum_{j=0}^{n-k}\sum_{i=1}^{k} (-1)^{i+1}A(n-j-i, k-i)\\$$ Some intial conditions that it holds are as follows: $$ n, k > 0\\ A(n, 0) = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A(n, ...
1
vote
2answers
46 views

Help with induction on a recursive sequence.

I'm currently working on this problem: At first, this looked like a pretty straightforward induction problem. But, once I started working on (b), I ran into an issue. I can show that my base case ...
0
votes
1answer
29 views

Method for solution to a recurrence

Is there a closed form solution or tight bound to recurrence $T[n]=k\cdot T[n^{1/c}] + (\log n)^{r}$ with $k,c,r\geq1$ and $T[n]=O(1)$ if $n\leq2$?
3
votes
1answer
41 views

Recurrence $a_j = \frac{n}{n-j} + \frac{j}{n-j} a_{j-1}$

Let $n\in \mathbb{N}$. How to solve the recurrence $$a_j = \frac{n}{n-j} + \frac{j}{n-j} a_{j-1}$$ for $1\leq j <n$, and $a_0=1$? I calculated it for some $n$s: $n=2: [1, 3]$ $n=3: [1, 2, ...
0
votes
0answers
18 views

Can the theory of difference equations yield insight into differential equations?

I'm currently taking a course in applied mathematics and MATLAB where basically we learn some theory and then apply it in practise to for example approximate integrals and differential equations. We ...
0
votes
1answer
24 views

Solving of basic recurrence relation

let us suppose we have following recurrence relation $T(n)=T(n-1)+1$ where $T_{0}=1$ we need to find homogeneous solution and particular solution , for homogeneous solution, we have $T(n)-T(n-...
1
vote
0answers
20 views

Slowest-growing divisibility sequence?

There are divisibility sequences of the form $\frac{p^k-1}{p-1}$ which have the property that if $a \mid b$, then $f(a) \mid f(b)$, ensuring (among other things) that only prime indices of the ...
1
vote
2answers
62 views

Given $S_n = \sum \dots$ and $a_n = \sum \dots$ prove that $a_n = S_n + {1\over n\cdot n!}$

I'm trying to solve the following problem: Let: $$ \begin{align} S_n &= 2 + {1\over2!} + {1\over3!} + {1\over 4!} + \dots + {1\over n!} \\ a_n &= 3 - {1\over 1\cdot2\cdot2!} - {1\over 2\...
1
vote
1answer
66 views

The Periodic Collatz Conjecture

Consider the function $$f(n)=\begin{cases}n/2&\mbox{if }n\mbox{ is even}\\3n+1&\mbox{otherwise}\end{cases}.$$ Starting from any positive integer $x_0$, we can iterate the sequence $x_1=f(x_0)...
2
votes
2answers
66 views

$s_n=s_{n-1}+(n-1)s_{n-2}$ prove $s_n>\sqrt{n!n}$ for $n\ge4$

Define sequece as follows: $s_1=1,~s_2=2, s_n=s_{n-1}+(n-1)s_{n-2}$. I want to prove that $s_n>\sqrt{n!n}$ for $n\ge4$. I'd tried to use traditional induction on $n$, but it involves both two terms ...
0
votes
2answers
34 views

Series solution to an ODE always giving me 0

I have the ODE $$y''-9x^4y=0,$$ and I want a series solution of the form $$y(x)=\frac{1}{\sqrt{3}x}e^{x^3}\sum_{n=0}^\infty a_n x^{n\alpha}$$ for some constant $\alpha$. Through all my attempts, I ...
0
votes
4answers
61 views

Prove there exist infinite subsequences of $x_{n+1} = x_n + 2^n$ all members of which are divisible by $3$

First, let $p \in \mathbb{N}$, and consider the following sequence $x_1,x_2,\ldots, x_n$ recursively defined: $$ \begin{cases} x_1 = p \\ x_{n+1} = x_n + 2^n \end{cases} $$ I want to show that,...
0
votes
0answers
67 views

Solving $(n+1)X^{n+1}-(n-1)X^{n}-(n-1)X + n+1 =0$ in $\mathbb{C}$

I have been trying to solve the following equation without any success: $$(n+1)X^{n+1}-(n-1)X^{n}-(n-1)X + n+1 =0$$ I already tried to use the known formula: $$x^{n+1} + \frac{1}{x^{n+1}} = \left( ...
7
votes
4answers
98 views

Find a recursive definition of this sequence

I always have some difficulty with problems of this type, and I was wondering if there was a typical trick that makes it reasonable. Let $W_n$ be the number of words of length $n$ formed with the ...
-1
votes
1answer
38 views

Inductive proof for recursive formula with multiple recursive references

This one is hard for me due to multiple recursive statements in the definition, and I have difficulty with inequalities. $a_1=1$ $a_2=1$ $a_3=1$ $a_{n+3} = a_{n+2}+a_{n+1}+a_n$ Prove that for ...
0
votes
1answer
39 views

Solving recurrence relation $T(n) = T(n/3) + T(n/2) + n^3$

Solve the recurrence relation $T(n) = T(n/3) + T(n/2) + n^3$. Could someone help me with this question here? I have tried the problem using recurrence tree but it starts getting complicated pretty ...
0
votes
1answer
38 views

Calculating Pascal's Triangle N-th row - why does this work? [closed]

I encountered this solution to the problem in the title (calculate Pascal's Triangle $N$-th row). The main point is the calculation within the loop - I am trying to figure out the meaning of it: ...