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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions tagged [recurrence-relations]

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

0
votes
0answers
17 views

First Order Nonlinear Recurrence Relation

I am trying to solve the closed formula for $x_n$ given the first order non-linear recurrence relation below. Unlike linear recurrences with direct solutions, I can't find any good reference for non-...
1
vote
1answer
34 views

Number of points that can be reached by following a certain pattern of jumps

A frog begins at $P_0 = (0,0)$ and makes a sequence of jumps according to the following rule: from $P_n = (x_n, y_n),$ the frog jumps to $P_{n+1},$ which may be any of the points $(x_n + 7, y_n + 2),$ ...
-3
votes
1answer
79 views

Define $g(n):=f(n!)$. We want to find a closed formula for $g(n)$ [on hold]

I am trying to understand the following question, and honestly have no idea from where to start it seems like it asking for factorial of $n$ terms in a form of $g(n)$? Define $g(n):=f(n!)$. We want ...
2
votes
0answers
30 views

Divisibility of a Evenly Spaced Binomial Coefficient Series

By this paper, it can be shown that for $n>0$ and $N\in\mathbb{N}$ $$\sum_{k=0}^n\binom{Nn}{Nk}=\frac{2^{Nn}}{N}\sum_{k=0}^{N-1}(-1)^{kn}\cos^{Nn}\left(\frac{k\pi}{N}\right)$$ Now, for a recursive ...
0
votes
1answer
17 views

Recurrence of $\{0,1,2,3\}^n$ tuples with the property that no elements is followed immediately by itself

For $n \geq 1$, let $t_n$ denote the number of elements in $\{0,1,2,3\}^n$ which have the property that no elements is followed immediately by itself (i.e. we don't allow $\{...,0,0,...\}$ or $\{...,2,...
0
votes
1answer
38 views

Finding a Recurrence Relation for a binary string with n digits that do not contain 000

Consider binary strings with $n$ digits (for example, if $n=4$, some of the possible strings are 0011, 1010, 1101, etc.) Let $z_{n}$ be the number of binary strings of length n that do not contain ...
1
vote
3answers
44 views

Prove by induction that $n^2 + n + 1 \forall n\geq 1$ given the following recurrence relation [on hold]

My question is as follows: Consider the following recurrence relation: $a_{n} = a_{n-1}+2n$, with $a_{1}=3$ Prove by induction that $a_{n}=n^{2}+n+1 \forall n\geq 1$ I have no idea how to even ...
2
votes
1answer
69 views

integrality of terms of a sequence

The sequence $(a_n)_{n \ge 1}$ is defined by $a_i=i$ for $i=1,2,3$ and satisfies $$a_{i}=\dfrac{a_{i-1}a_{i-2}+7}{a_{i-3}}, i \ge 4.$$ The question is to prove that all terms of the sequence are ...
1
vote
1answer
25 views

Number of ways a board can be found within a game

In a game of Chomp, two players alternately take bites from a 5-by-7 grid of unit squares. To take a bite, a player chooses one of the remaining squares, then removes ("eats") all squares in the ...
0
votes
1answer
54 views

Existing $a$ and $b$ that given sequence doesn't contain prime number

Does exist $a$ and $b$, which are coprime positive integers that sequence defined below contains only composite numbers: $$x_0=a, \ x_{n+1}=b+\prod_{i=0}^n x_i ?$$ I suppose that it doesn't exist, ...
0
votes
2answers
33 views

Solve the second order linear non-homogeneous difference equations

Consider the following linear difference equation $$ f_{k} = 1 + \frac{1}{2} f_{k+1} + \frac{1}{2} f_{k-1}, 1\le k \le n-1$$ with $f_0 = f_n = 0$. How do I find the solution? I consider the ...
0
votes
2answers
26 views

Construct a matrix from a number sequence [on hold]

I have the following problem that I cannot figure out how to approach, how would you do it? Consider the number sequence given by $x_0 = 0$ $x_1 = 1$ $x_{n+2} = 3x_{n+1}-2x_n$ Construct a ...
1
vote
0answers
23 views

Consistency of system of recurrence relations

I believe I am having some trouble understanding the difference between a system of recurrence relations and a linear system of linear/nonlinear equations, and I could not find much information about ...
0
votes
0answers
30 views

Convert recursive into explicit form

Recursively define $f_n \in C^\infty (\mathbb{R}^n,\mathbb{R}^n)$ through $f_2(y):=(y^1\cos y^2, y^1 \sin y^2)$ for $y=(y^1,y^2)\in \mathbb{R}^2$ and $f_{n+1}(y)=(f_n(y')\sin y^{n+1},y^1 \cos y^{...
0
votes
0answers
36 views

This Infinite Random Sequence?

I was working on Random sequence and LCG's when I found this recursive algorithm: $$X_{n+1}=[{\sqrt{n(X_n+1)}}]\%10$$ Where, $[x]$ is the floor function. When executed with $X_0=0$, the ...
-3
votes
1answer
16 views

recurrence relation and sigma notation

Can anyone help me and explain with sigma notation rules how does this equation solved The problem for me that $T(i)$ and $T(i-1)$ are inside sigma notation(not i) so i am confused. Please anyone ...
0
votes
0answers
20 views

Transform generating function into linear recurrence relation

This problem is inspired from here. Given a generating function $f(x)=\frac{p(x)}{q(x)}$ where $p(x)$ and $q(x)$ are irreducible polynomials, how to transform it into a linear recurrence relation?
3
votes
0answers
90 views

A two-variable recurrence relation for $\int_0^{\pi/2} t^n \cot^m (t) \, \mathrm{d} t$

I have found a general expression for the integrals $I_n$ discussed in this question in terms of $K_l^{(l)} \, , \, 0 \leq l \leq n \, , $ where $$ K_n^{(m)} \equiv \int \limits_0^{\pi/2} t^n \cot^...
3
votes
1answer
48 views

Perfect Squares In a Recurrence Relationship [duplicate]

If $$a_{n+3}=-a_{n+2}+2a_{n+1}+8a_n $$ for $$ a_0=a_1=a_2=1.$$ Then prove that $a_n$ is a perfect square.
2
votes
1answer
21 views

homogenous linear recurrence relation - need help with understanding the solution

I apologize if this question is far too obvious, but I'm a bit confused (and new to this subject). I have to solve the recurrence relation: $a_n=6a_{n-1}-9a_{n-2}$ $n=2,3,..$ Using Euler ...
1
vote
1answer
43 views

Solving a floored input linear recurrence relation

Need help solving: $$T(n) = T(n-1) + \binom{n-1}{\lfloor\frac{n-1}{2}\rfloor + 1}$$ for $n \geq 3$ and $T(1) = 1$, $T(2) = 2$ I believe the answer is $T(n) = \binom{n}{\lfloor\frac{n}{2}\rfloor}$, ...
1
vote
0answers
31 views

Multivariate recurrence solve

I am currently working on a project and have reduced much of the problem to a single recurrence equation: $$g(x,y)=1-\frac{1}{6}g(y,x-1)-\frac{1}{2}g(y,x)-\frac{1}{3}g(y+1,x-1)$$ $$g(0,a)=1$$ $$g(a,0)...
0
votes
3answers
25 views

Help solving a non-homogeneous recurrence relation

I have this recurrence relation: $$a_{n+1} + 2a_{n}+2a_{n-1} = ( n+3)\times2^n,$$ where $a_0= -\frac{2} {5} $, and $a_1=\frac{46}{5}$ So for the homogeneous part, I have $x^2+2x+2=0$ or $x=1$. ...
2
votes
0answers
26 views

Does there exist a nice closed form for multidimensional linear recurrence relations like those of single-dimensional ones?

If we have the recurrence relation $$\sum_{j=0}^k a_{n-j}c_j = 0$$ for all $n\geq k$ and $\lambda_1,\cdots,\lambda_s$ are the (complex) roots of $$P(\lambda) = \sum_{j=0}^k c_j\lambda^j$$ with ...
3
votes
1answer
32 views

Let $a_1=1, a_n=(n-1)a_{n-1}+1,n\ge 2.$ Find $n$ such that $n|a_n.$

Let $a_1=1, a_n=(n-1)a_{n-1}+1,n\ge 2.$ Find $n$ such that $n|a_n.$ My progress: Given recurrence can be rewritten as $\frac{a_n}{(n-1)!}-\frac{a_{n-1}}{(n-2)!}=\frac{1}{(n-1)!}$ $\implies a_n=(n-...
2
votes
1answer
97 views

Is Case 2 of my proof that $\sum_{i=1}^n a_i=\sum_{i=1}^n a_{\sigma(i)}$ correct?

Let $I_n=\{i\in\mathbb N\mid 1\leq i\leq n\}$, $(a_1,\cdots,a_n)$ be a finite sequence in $\mathbb N$, and $\sigma$ be a permutation of $I_n$. I've shown that there is a sequence $(s_1,\cdots,s_n)$ ...
7
votes
4answers
400 views

Justify: if $x\gt 0$, $\;\lim_{n\to\infty} \sqrt{n}\cdot{\overbrace{\sin\sin\cdots\sin}^{n\space\text{sines}}(x)}=\sqrt{3}$

I believe that I have managed to show that (if $x\gt 0$) $$\lim_{n\to\infty} \sqrt{n}\cdot{\overbrace{\sin\sin\cdots\sin}^{n\space\text{sines}}(x)}=\sqrt{3}$$ I did this by defining a sequence as $a_0=...
1
vote
3answers
131 views

$a_n-a_{n-1}+\frac{2}{n}a_{n-2}=0$. Is $\{a_n\}$ eventually positive/negative, or $a_n=O(n^{-2})$?

So there is a recusive sequence $\{a_n\}$ with \begin{equation}a_n-a_{n-1}+\frac{2}{n}a_{n-2}=0, \quad (n\geq 2)\tag1 \end{equation} values of $a_0$ and $a_1$ being arbitrary. Is it true that: ...
1
vote
1answer
30 views

Evaluating $\sum_{i=0}^{k-1} 4^i(i-1)$ for recurrence relation exercise [duplicate]

I need help to solve the following sum: $$\sum_{i=0}^{k-1} 4^i(i-1)$$ I'm doing some exercises about recurrence relations in algorithms and this sum came up. The exercise stands like: $$T(n) = \...
1
vote
2answers
98 views

How to solve given recurrence relation for a given n and k?

Given a recurrence relation as follows: $$ T(n,k) = \begin{cases} 1, & \text{if $n \leq k$} \\ T(n-1,k) + T(n-2,k) +... + T(n-k,k) & \text{otherwise} \end{cases} $$ Find $T(n,k)$. Link to ...
0
votes
3answers
35 views

Recurrence relation with a matrix?

Let $ \mathbf{M} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ and $\mathbf{X}_{n} = \begin{bmatrix}x_n \\ y_n \end{bmatrix}$. Solve $\displaystyle \mathbf{X}_{n+1} = \mathbf{MX}_n$ for $n \...
3
votes
1answer
69 views

Solve the Recurrence : $T(n)=3T(n/3) +\frac{n}{\log(n)}$.

This question has been asked before but doesn't solve my doubt. After Solving the recurrence relation $$ T(n) = 3T(n/3) + \frac{n}{\log{n}}$$ I get following equation $$ T(n)=3^kT(n/3^k) + \frac{n}{\...
0
votes
1answer
32 views

polynomial in recurrence relation using matrrix exponential [closed]

I have my recurrence relation as f(n) = a*f(n-1) + b*f(n-2) + n*n how to solve that relation using matrix exponential I have tried like ...
0
votes
0answers
29 views

Simple recurrence relation

Assume that for a function $f_{a,b}(x)$, for which it holds $0<f_{a,b}(\cdot)<1$ following recurrent relation holds: $$f_{a,b}(x)=\frac{a}{b-x(1-f_{a+1,b+1}(x))}=\frac{a}{b-x+xf_{a+1,b+1}(x)}. $$...
2
votes
1answer
39 views

Minimum number of nodes present in binary tree with constraint $|P – Q| ≤ 2$

Question Consider a binary tree; define its height as $0$ if it consists of a single node, and $1$ plus the maximum height of its subtrees otherwise. For a generic node $u$ in the tree, let $P(u)$ ...
0
votes
0answers
20 views

How to define summation recursively? [duplicate]

I have attempted to define $s_n=\sum_{i=1}^n a_i=a_1+\cdots+a_n$ in a valid manner, but I'm not sure if my extraction of $(s_i\mid 1\leq i\leq n)$ from $(p_i\mid i\in\mathbb N)$ contains any error. ...
0
votes
3answers
32 views

Using a summation factor to solve a recurrence

On Princeton's Analysis of Algorithms, they discuss solving recurrence relations and they come across a line that I can't seem to decipher \begin{align} n(n-1)a_n &=(n-1)(n-2)a_{n-1} + 2(n-1)\\ &...
0
votes
1answer
61 views

Complexity of $T(n)=T(n - \sqrt{n})+n$

What is complexity of $T(n)=T(n - \sqrt{n})+n$ I tried to solve this with a few methods that I know but none of them helped me. So I decided to ask you for help.
1
vote
1answer
28 views

Recurrence relationer of intersection points formed by the diagonals of a convex polygon.

Derive a recurrence relation to represent the number of intersection points formed by the diagonals of a convex polygon with n vertices. Show that the solution of the recurrence relation is $\binom n4$...
0
votes
0answers
62 views

Recurrence relation of $1, 3, 3, 15, 5, 35, 7, 63, 9, 99, 11, 143, 13$

I found this sequence: $$1,3,3,15,5,35,7,63,9,99,11,143,13...$$ I'm looking for its recurrence relation, and/or its closed form. My take: it's easy to see that when $n\geq4$ and is even, $a_n=a_{n-...
2
votes
1answer
48 views

Solving a Recurrence Relation with Characteristic Roots: is my algebra bad, or is it something else?

I am having a considerable amount of trouble solving this problem. I have shown my work below and am wondering if somebody can show me where I have messed up. I have been working on this for a few ...
4
votes
1answer
110 views

How to get a recurrence relation from an expression with maximum

There is a certain function $F(r,s)$ (where $r\geq -1$ and $s\geq 0$ are integers) that satisfies the following relation: $$ \max\big[2 F(r,s) - F(r-1,s) - F(r-1,s-1)~~~,~~~F(r+1,s+1) - F(r-1,s)\big] ...
0
votes
1answer
130 views

How to justify the definition of summation $s_n=\sum_{i=1}^n a_i=a_1+\cdots+a_n$?

I read https://www.wikiwand.com/en/Summation#/Formal_definition and found that they define summation via recursion, so I decided to formalize the proof that that this definition is actually valid. I'...
-1
votes
0answers
20 views

generating function for recursive formula of two variables

I have a pice-wise function which is divided into even and odd parts as you can see in the following. I hope to know if there's a generating function that fit this recursive relation. $$ f(x) = ...
2
votes
1answer
64 views

Class of fractal curves derived from recursion on the base-2 representation of the integers

Consider the recurrence $\displaystyle T(n) = \begin{cases} 1 &\text{if } n = 0 \\ 0 &\text{if } n = 1 \\ T(\lfloor n/2\rfloor) + T(n \bmod 2) &\text{otherwise} \end{cases} $ If you ...
0
votes
1answer
53 views

Recurrence Relation numerical.

i've this recurrence relation to which i need to find the general numeric function, $a_r$ - $5a_r$$_-$$_1$ + $8a_r$$_-$$_2$ - $4a_r$$_-$$_3$ = $r*2^r$ $...(i)$ i get the homogeneous solution ...
1
vote
1answer
32 views

Combinations - Solving recurrence relation in 2 variables without using generating functions

I know that there are similar questions here solving 2 variable recurrence and combinations recurrence equation, but both of them use generating functions to solve this. Is there any other way to ...
4
votes
1answer
80 views

Solve Recurrence Relation $a_k=(a_{k-1})^2-2$

$$a_k=\left(a_{k-1}\right)^2-2$$ $a_0=\frac{5}{2}$ Then find $$P=\prod_{k=0}^{\infty} \left(1-\frac{1}{a_k}\right)$$ My try: I rewrote the Recurrence equation as $$a_k+1=(a_{k-1}-1)(a_{k-1}+1)$$ $...
0
votes
0answers
30 views

Solving $f(n) = n \log(n)$ using this version of Master theorem.

I am trying to solve this $T(n)= 2T(n/2) + n\log(n)$ using this version of master theorem in my lecture notes: But I cannot be able to solve it. But if I use other version master theorem found on ...
0
votes
1answer
57 views

The limit of a sequence $u_{n+1}=\exp(u_n)+u_n$ [closed]

Please help me to find the limit of this sequence : $ u_0=-2017\;$ and $\; u_{n+1} =e^{u_n}+u_n $ I don't know if the limit exist or not.