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

learn more… | top users | synonyms (2)

1
vote
2answers
110 views

How many $a$-nary sequences of length $b$ never have $c$ consecutive occurrences of a digit?

Let $S(a,b,c): = \#\{a$-nary sequences of length $b$ without $c$ consecutive occurrences of a digit$\}$. For example, $S(2,n,3)$ would be the number of binary sequences of length $n$ without $3$ ...
1
vote
3answers
47 views

Finding the limit of a recurrence relation?

I have a sequence defined by the relation $$x_{n+1} = \alpha x_n + (1-\alpha)x_{n-1}$$ for $n\geq 1$, and I want to find the limit in terms of $\alpha , x_0,x_1$. I tried to do this by setting up a ...
1
vote
2answers
81 views

Find the general term of the recursive relation $a_{n+1}=\frac{1}{n+1}\sum\limits_{k=0}^n a_k 2^{2n-2k+1}$

I need to find the general term of the recursive relation $a_{n+1}=\frac{1}{n+1}\sum\limits_{k=0}^n a_k 2^{2n-2k+1}$ I know it's the central binomial sequence but I can't find a way to show it. ...
2
votes
1answer
117 views

Closed form solution to a recurrence relation (from a probability problem)

Is there a closed form solution to the following recurrence relation? $$P(i,j) = \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$ where $P(i,j)=0$ for $j<5$. The ...
0
votes
2answers
208 views

Recurrence relation for words length $n$

I need to solve following question: "An alphabet consists out of 4 letters $a,b,c,d$ and 3 numbers $1,2,3$. Find the recurrence relation for the number of words of length $n$ where no two numbers are ...
1
vote
2answers
41 views

First order recurrence relation

I have to solve this relation: $$a_1 = k \\ a_n = \frac{10}{9} a_{n-1} + k + 1 - n$$ (k is constant) How can I do it??
4
votes
1answer
70 views

Non-linear Recurrence relation

I am concerned to solve the recurrence relation $T(n)=nT^2\left(\frac{n}{2}\right)$ with initial condition T(1)=6. I have tried to do some transformation like $N=2^k$ and some other things like that ...
0
votes
3answers
84 views

Finding a reduction formula for this integral

Let $$I(n)=\int_0^1 (x-x^2)^n dx .$$ Mainly, what I'm trying to get is a recurrent form of this integral that probably involves $I(n-1)$. My attempt ...
1
vote
0answers
82 views

Proof that $\forall x \in \mathbb{R}, \forall n \in \mathbb{N}: (f(x))^n = f(nx)$ only has solutions of the form $f(x) = c^x$ for some constant $c$

I am looking for a proof (or a counterexample I suppose) that the recurrence equation (is that the right term here?) $(f(x))^n = f(nx)$ only has a solution of the form $ f(x)=c^x$ for some ...
1
vote
1answer
62 views

How to convert linear recurrence to a tiling question

If I have some linear recurrence of form $$f(n) = a_1f(n-1) + a_2f(n-2) + a_3f(n-3) + \cdots + a_kf(n-k)$$ How does this translate to tilings? For example the Fibonacci sequence is the same as ...
0
votes
1answer
115 views

Solve the recurrence relation $f(n) = f(n - 1) + f(n - 2) + f(n - 3)$

This is a problem I was playing with that troubled me greatly. $f(n) = f(n - 1) + f(n - 2) + f(n - 3)$ $f(1) = f(2) = 1$ $f(3) = 2$ So, the goal is to try and find a solution for f(n). I tried ...
1
vote
1answer
37 views

Help with recurrence equation

I need to solve the following recurrence equation $p_i =\begin{cases} r(p_{i-1}+p_{i+2}) &\mbox{if } i \text{ is odd} \\ (1-r)(p_{i-1}+p_{i}) & \mbox{if } i \text{ is even} \end{cases} i ...
2
votes
1answer
135 views

How can I express such function as known functions or power series?

$$\int_0^x \cfrac{1}{1+\int_0^t \cfrac{1}{2+\int_0^{t_1} \cfrac{1}{3+\int_0^{t_2} \cfrac{1}{\cdots} dt_3} dt_2} dt_1} dt =f(x)$$ $$\int_{0}^{x} \frac{1}{n+h_{n+1}(t)}{d} t=h_n(x)$$ ...
6
votes
3answers
92 views

Please solve this recurrence relation question for $8a_na_{n+1}-16a_{n+1}+2a_n+5=0$

Suppose $a_1=1$ and $$8a_na_{n+1}-16a_{n+1}+2a_n+5=0,\forall n\geq1,$$Please help to sort out the general form of $a_n$. Here are the first a few values of the series. Not sure if they are useful as ...
0
votes
0answers
48 views

Solution to the recurrence relation with two equations

I am given : $$\begin{cases} v(0) = 0 \\ v(n)=\frac{1}{3}v(n+1)+\frac{2}{3}v(n-1)+1 & \text{ for } n < m\\ v(n)=k+v(1) & \text{ for } n \ge m\\ \end{cases}$$ The general solution to ...
3
votes
5answers
729 views

recurrence relation, linear, second order, homogeneous, constant coefficients, generating functions

How to solve this by using the generating functions? What is the possible solution for this? recurrence relation $$ a_n = 5a_{n-1} – 6a_{n-2}, n \ge 2,\text{ given }a_0 = 1, a_1 = 4.$$ Thanks.
2
votes
0answers
138 views

Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...
2
votes
1answer
62 views

How to solve this specific recurrence relation

I'm trying to solve the following recurrence relation for $\alpha_j$, for which Mathematica is not helpful. $$ \lambda\alpha_j + (j+1)\alpha_{j+1} = \sum_{\mu = ...
2
votes
3answers
6k views

Closed form solution of recurrence relation

I am asked to solve following problem Find a closed-form solution to the following recurrence: $\begin{align} x_0 &= 4,\\ x_1 &= 23,\\ x_n &= 11x_{n−1} − 30x_{n−2} ...
4
votes
4answers
293 views

Explicit formula for a recursion

How can you express the following recursion explicitly? \begin{cases} T_0 = 1\\ T_n = 1 + 2\cdot T_{n-1}\\ \end{cases}
0
votes
2answers
240 views

Integral of $\sin^n(x)$, recurrence relation, some properties

Practicing the manipulation of recurrence relations, I'm stuck on this : Defining $I(n)=\int_{0}^{\pi/2}sin^n(x)dx$, I got the recurrence relation $nI(n)=(n-1)I(n-2)$ for $n\ge2$. Now I'm also ...
1
vote
1answer
79 views

Example for finite dimensional analog of integral transforms

I understand that integral transforms are generalisations of the dot product of functions that could be interpreted as infinite dimensional vectors. The most significant advantage then is that ...
0
votes
1answer
25 views

Geometric recurrence, prove $g(k)=3g(k-1)-2g(k-2) is g(n)=2^n+1$

Geometric recurrence, prove gk = 3g(k-1) - 2g(k-2) is gn = 2n+1 using iteration. g1 = 3, g2 = 5 So, g3 = 3g(2) - 2g(1) = 3(5) - 2(3) = 9 <---- *which is 23+1 = 8+1 = 9 I'm unsure how to ...
4
votes
4answers
267 views

Finding the billionth number in the series: $2, 3, 4, 6, 9, 13, 19, 28, 42, \ldots $?

Series is defined as $$a_{n+1} = \lfloor\frac{3\cdot a_n}{2}\rfloor,\qquad a_0 = 2$$ It can be viewed as the number of animals starting from a single pair if any pair of animals can produce a single ...
3
votes
1answer
115 views

2D Pattern in recursive digit sum of consecutive x^n

Take the recursive decimal digit sum of consecutive binary numbers $2^n$ as $n \to \infty$. You'll see something like this: n 2^n (recursive) sum of digits ...
1
vote
2answers
35 views

Not sure how to do Non-Homogeneous Recurrence Relations

I have a sample exam paper, and the answer is given, but I can't work out the answer from the question: Find the solution of: $a_n = \frac{1}{3}a_{n-1} + 2$ using $a_0 = 4$ Given Answer: $a_n = ...
1
vote
0answers
33 views

Solving a recurence system

Find a function $f(x,y) : \mathbb{N}^2 \to \mathbb{N}^2$ such that: $1 + f(x+1,y) - f(x,y) = a$ $1 + f(x, y+1) - f(x,y) = b$ $k + f(x-k, y) - f(x,y) = c \space \forall k \leq x$ $k + f(x,y-k) - ...
-1
votes
1answer
33 views

Understanding non homogeneous recurrence

Find a particular and then the general solution for the recurrence relation $a_n = 7\cdot a_{n−1} − 30 \cdot 2^n$ Trying to understand this equation.... We have been given a general formula for this ...
0
votes
1answer
49 views

Solving Recurrence Relation Question

How do i solve recurrence relations like $a(n) = 3a(n/2) - 2a(n/4); a(1)=3; a(2)=5$? I don't think I can draw a recursion tree since there's no function like $2n$ at the end.
1
vote
3answers
60 views

Understanding a recurrence relation question.

A computer system considers a bit string a valid codeword if and only if it does not contain $3$ consecutive zeroes. Thus $010010$ is a valid codeword of length $6$ while $011000$ is not. Let $a_n$ be ...
-3
votes
1answer
66 views

N balls of k colors on a cirlce, no two neighboring balls have same color - recursive algorithm

Suppose we have N balls of k different colors. What is the number of arrangements of these N balls on a circle with no two neighboring balls having the same color? Actually, the task is to make up a ...
1
vote
2answers
43 views

Recurrence with multiplication

Let $\{a_{n}\}$ be a sequence of nonnegative numbers such that $a_{n} = 2^{n}a_{n - 1}^{3/2}$. If $a_{1}$ is sufficiently small, why must $a_{n} \rightarrow 0$ as $n \rightarrow \infty$?
0
votes
1answer
58 views

How often does $p^k$ divide the Fibonacci numbers?

I would like to know about the Fibonacci numbers $F_n = 1,1,2,3,5,8, \dots$ in $\mathbb{Z}/p^k\mathbb{Z}$. $$ \mathbb{P}[p^k \text{ divides } F_n ] = \frac{\#\{1 \leq n\leq N: F_n \equiv 0 \mod ...
2
votes
1answer
50 views

Recursive formula for creating a specific string

I have 5 characters ${a,b,c,1,2}$. $a_n$ is the number of strings I can create for $n$ length. I can't have the following sequences in a string: $a1$, $b2$ and any sequence of numbers $(12, 21)$. For ...
0
votes
2answers
54 views

Closed form for a strong recurrence relation

Let $\alpha_n$ be a sequence of complex numbers and consider the sequence $b_n$ defined by the (strong) recurrence relation : $$b_{n+1} = \sum_{k=0}^n \alpha_{n-k} b_k$$ with the initial condition ...
2
votes
3answers
43 views

Recursive integration

The integral I have is $$I_{n} = \int^{\pi/2}_{0} \cos^{2n+1}y \ \mathrm{d}y$$ And I have found $I_{n} = \frac{2n}{1+2n}I_{n-1}$ but I want to express $I_{n}$ in a form without $I_{n-1}$ how do I do ...
0
votes
0answers
33 views

Convergence rate of $x_{k+1}=3x_k^2/n+3$

I've found the following claim in a slightly different form here (page 4, bottom of the left column) Starting from $x_0\le n/3$, the recurrence equation $$3\le ...
7
votes
3answers
4k views

I have a problem understanding the proof of Rencontres numbers (Derangements)

I understand the whole concept of Rencontres numbers but I can't understand how to prove this equation $$D_{n,0}=\left[\frac{n!}{e}\right]$$ where $[\cdot]$ denotes the rounding function (i.e., ...
1
vote
0answers
71 views

Analytic Function Derived From Recursive Reverse Taylor Series?

Given the following recursive relation: $a_0 = 1,$ $a_n = a_{n-1}(p-2q)+2(-p)^n$ is there a simple function that has this as its Taylor series, i.e. $f(x) = \sum_{n=0}^{\infty} \frac{a_n}{n!}x^n$ ...
13
votes
3answers
230 views

For $x_{n+1}=x_n^2-2$, show $\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$

Suppose $x_0:=2\sqrt{2}$ and $x_{n+1}=x_n^2-2$ for $n\ge1$. We have to show $$\lim_{n\to\infty}\frac{x_n}{x_0x_1\cdots x_{n-1}}=2$$ Establishing convergence is pretty direct but I'm having trouble ...
0
votes
1answer
38 views

generating functions for $S(n,3)$

I would like to find a closed formula for the Stirling numbers of the second kind $S(n,3)$ or the number of ways to partition a set of 3 elements into 3 sets. I know that $S(n,3)=3S(n-1,3)+S(n-1,2)$ ...
1
vote
1answer
57 views

Solve $X_n=\lfloor \sqrt{X_n} \rfloor+X_{n-1}$

How do I solve $X_n=\lfloor \sqrt{X_n} \rfloor+X_{n-1}$? The initial terms are $1,2,3,5,7,10,13,17,21,26,31$. A search on oeis.org/ gave $\lfloor n/2 \rfloor\cdot\lceil n/2 \rceil$ + 1 which should be ...
2
votes
3answers
161 views

Fibonacci polynomials and factorization redux

I recently asked a question about factorizing a certain expression involving Fibonacci and Lucas polynomials. That question had a very simple and nice answer, but now I've come across another similar ...
0
votes
0answers
32 views

What is the asymptotic bound of the recurrence : $T(n)= 2T\frac{n}{2}+\log n$?

I have managed to reach upto : $T(n) = 2.n.\log n - \log n - [2+2.2^2 +3.2^3 + \dots\log_2 n.2^{\log_2 n}]$ I m stuck here and not getting any clue how for solving the arithmetico-geometric series. ...
1
vote
0answers
39 views

$\cos(2\arccos(\frac{a}{a+1})x$

I have trying to prove that this cosine map: $$\frac{r}{4}((a+1)\cos\left(2\arccos\left(\frac{a}{a+1}\right)\ \left(X_n-\frac12\right)-a\right)$$ is a logistic map. What I have done so far: Using ...
1
vote
5answers
120 views

A non-homogenous linear recurrence: Why does my method fail?

I'm trying to solve this recurrence relation: $$a_m = 8 \cdot a_{m-1} + 10^{m-1}, a_1=1$$ By the change of variable $\displaystyle b_m = \frac{a_m}{10^m}$ I obtained this linear non-homogenous ...
2
votes
2answers
79 views

Zeroes of polynomial

$$c_1,c_2 \text{ are polynomial's }g(x)=x^2+ax+b \text{ roots } \Leftrightarrow \begin{cases} g(c_1)=c_1^2+ac_1+b=0 \\ g(c_2)=c_2^2+ac_2+b=0 \end{cases}$$ Prove that for every polynomial with integer ...
2
votes
2answers
37 views

Find general solution

I want to find the general solution for the following : $$t(n)=t(\frac{n}{4})+\sqrt{n}+n^2+n^2log_{8}n $$ Note: $n=4^k$ $t(n)=t(4^k)=t_{k}$ $$t_{k}=t_{k-1}+2^k+16^k\cdot \frac{2}{3}k$$ ...
1
vote
1answer
56 views

Recurrence Relation all general solutions

I need some help solving the following recurrence relation: $a_n = 4a_{n-1} - 4a_{n-2} + (n+1)*2^n$ What I've tried: a) Find the general solution of the associated linear homogenous recurrence ...
1
vote
1answer
76 views

Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...