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

learn more… | top users | synonyms (2)

4
votes
1answer
83 views

Is there a nice recurrence relation for $n^n$

I know there is a nice equation for $n!$, but is there one for $n^n$? I was thinking you could get it with the fact $n^n=a^{n\log_an}$ but I can't seem to make the needed jump. Edit: It was suggested ...
4
votes
2answers
160 views

Optimization of parameter for recursive Cauchy sequence

I have the following recursive sequence I'm analyzing: $$V_0 = 50, V_1 = (1-10k)V_0,$$ $$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$ where $k > 0$ is a parameter that I'm investigating by running ...
1
vote
2answers
38 views

Linear Recurrences

I was working on linear recurrence... But I am having trouble with it. $a_0 = 1; a_1 = 2; a_k = 4a_{k-1} - 2a_{k-2}$ I found $a_2$ which is $$4a_1 - 2 a_0=4\cdot2 - 2\cdot 1 = 6$$ I found $a_3$ ...
2
votes
4answers
212 views

Showing a particular recurrence is constant

A sequence, $ ( a_n ) _ { n \in \mathbb{N}} $, is constructed by selecting a value of $ a_0$, and then successively forming the following elements from the equation. $$ a_n = 2- \frac12 a_ { n- 1} $$...
1
vote
3answers
64 views

First order difference equation. Solve $u_{n+1}=3u_n+2$.

First order difference equation. Solve $u_{n+1}=3u_n+2$ with $u_0=0$ My notes are very sparse on this topic, so I need some help solving what should be an easy question. I would really appreciate ...
1
vote
1answer
25 views

Find a formula for $\langle X_n\rangle$ which is defined recursively as follows

$X_1=a$, $X_2=b$ and $X_{n+2}=(X_n+X_{n+1})/2$ Find a formula for $\langle X_n\rangle$ valid for each $n\in\mathbb N$. I wrote a few terms in this sequence and tried to derive a formula. But I ...
1
vote
1answer
55 views

Select $k$ non overlapping segments from $n$ points

We have $n$ points , say labeled from $1$ to $n$. We have to select $k$ segments from it so that no $2$ overlap. One possible solution would be by using a recurrence relation $f(k,n)=\sum i*f(k-1,n-...
-1
votes
1answer
50 views

Solving This Particular Recurrence Equation [closed]

Let $\lambda \in \mathbb{R}$. Is there any way I could solve this recurrence? $$ a_k=-\dfrac{\lambda^2 a_{k-4}}{k(k+1)} $$ where $$ a_0\in\mathbb{R} \quad\quad a_1\in\mathbb{R} \quad\quad a_2=...
0
votes
4answers
100 views

Solve the reccurence $a_n= 4a_{n−1} − 2 a_{n−2}$

Solve the recurrence $a_n = 4a_{n−1} − 2 a_{n−2}$ Not sure how to solve this recurrence as I don't know which numbers to input to recursively solve?
1
vote
1answer
113 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
20
votes
2answers
447 views

What is the integral of $e^{a \cdot x+b \cdot y}$ evaluated over the Koch Curve

What is $$\int_{K} e^{a \cdot x+ b \cdot y} \mu(x,y)$$ where $K$ is the Koch curve and $\mu(x,y)$ is a uniform measure look here. Attempt: I can evaluate the integral numerically and I have derived ...
1
vote
2answers
56 views

Solve the recurrence $a_n=7a_{n-1}-10a_{n-2}$ where $a_{0}= 3$ and $a_{1}=3$

Solve the recurrence $a_n=7a_{n-1}-10a_{n-2}$ where $a_{0}= 3$ and $a_{1}=3$ how can a $a_{0}$ and $a_{1}$ both equal $3$?
0
votes
3answers
38 views

Linear recurrence

Having trouble solving this type of question, I can solve it when the equation equates to 0 however when it equates to something like $5(3)^n$ I get stuck. here's the question: $$(1) \quad u_n - 4u_{...
8
votes
1answer
392 views

Challenging recurrence relation problem

I am starting out with the following: $$ \frac{d^n}{dx^n}[g(x)^{f(x)}] = \sum_{c=0}^n g(x)^{f(x)-c}\lambda_{n,c}(x) $$ Therefore: $$ \frac{d^{n+1}}{dx^{n+1}}[g(x)^{f(x)}] = \sum_{c=0}^{n+1}g(x)^{f(...
4
votes
2answers
76 views

What happens to a system of difference equations when A is non-diagonalizable?

Suppose I have a system of linear difference equations $$ \mathbf{x}_{n+1} = A \mathbf{x}_n \>.$$ If $A$ is diagonalizable, then it can be shown that the system asymptotically approaches $\vec{0}$...
0
votes
1answer
49 views

Find a linear reccurrence relation where a(n) is the number of subsets of {1,2,3,…,n} not containing three consecutive numbers.

Find a linear constant coefficient for the recurrence relation $a(n)$ where $a(n)$ is the number of subsets of $\{1,2,3,\dots,n\}$ not containing three consecutive numbers. So $a(n)$ must have a ...
2
votes
1answer
572 views

Define a recursive sequence for the following formula f(n) = n(n+1)

Define a recursive sequence for the following formula f(n) = n(n+1). Preferably one only defined by previous $a_n$ terms, i.e., no 'n' terms. If possible that is. So for example the following ...
2
votes
1answer
117 views

Master Theorem for solving recurrences question

Who can explain to me why $$T (n) = 4T (n/2) + n/ \log n \Longrightarrow T (n) = Θ(n^2) \tag{Case 1}$$ But for $$T (n) = 2T (n/2) + n/ \log n$$ ⇒ Master Theorem does not apply (non-polynomial ...
4
votes
1answer
76 views

How many strings of $\{0,1,2,3\}$ of length $n$ are there such that $0$ appears exactly once and $1$ appears an even number of times?

How many strings of length $n$ of the digits $\{0,1,2,3\}$ are there such that $0$ appears exactly once and $1$ appears an even number of times? My attempt: define $a_n$ to be a sequence of such ...
5
votes
3answers
4k views

Recurrence relation for number of bit strings of length n that contain two consecutive 1s

I'm pulling my hair out over a review question for my final tomorrow. Find a recurrence relation (and its initial conditions) for the number of bit strings of length n that contain two consecutive ...
0
votes
1answer
30 views

Recursive sequences and solutions

Let $s_0$, $s_1$, $s_2$, . . . be a recursive sequence defined by $s_0 = 4$,$s_1 =3$, $s_n$ =$−6s_{n−1}$ − $9s_{n−2}$ for all integers $n\ge2$ Find an expression for $s_n$ in terms of $n$ that holds ...
2
votes
1answer
91 views

Intuitive explanation for Derangement

The recurrence relation for Derangement is as follows: Let $D_n$ denote the number of derangements of a set $\{1,2,3...n\}$ $D_n=(n-1)D_{n-1}+(n-1)D_{n-2}$ Can someone give and intuitive ...
1
vote
0answers
27 views

Deriving the Particular Solution to a Linear Discrete Dynamical System

In my lecture notes it says that for a linear dynamical system of the form $ f(x) = Ax $ where A is diagonalisable d x d matrix, with $ \left \{ v_1 , v_2, \cdots , v_d \right \} $ a basis for $ \...
1
vote
2answers
206 views

Solve by using substitution method $T(n) = T(n-1) + 2T(n-2) + 3$ given $T(0)=3$ and $T(1)=5$

I'm stuck solving by substitution method: $$T(n) = T(n-1) + 2T(n-2) + 3$$ given $T(0)=3$ and $T(1)=5$ I've tried to turn it into homogeneous by subtracting $T(n+1)$: $$A: T(n) = T(n-1) + 2T(n-2) + ...
1
vote
1answer
156 views

Prove this recurrence relation? (catalan numbers)

$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$ Where $C_n$ denotes the number of ways of writing a valid list of open and closed parentheses of length ...
0
votes
0answers
46 views

Maximum period-length in decimal chain-addition?

Decimal chain-addition $^*$ takes a finite initial "seed" string of decimal digits, say $x_1x_2...x_n$, and defines an infinite periodic string $x_1x_2...x_n...$ by iterating the following rewrite ...
4
votes
1answer
241 views

Help finding a closed form

I have the following function: $$\frac{2e^x}{e^{2x}+1+2x}=\sum_{n=0}^\infty \varepsilon_n\frac{x^n}{n!}$$ I would like to find a closed form for the $\varepsilon_k$. One thing that I do know is that ...
1
vote
3answers
31 views

transformation of a difference equation

How can I translate the difference equation $$x_{k+3}+4x_{k+2}+3x_{k+1}+x_k=2u_{k+2}$$ into a state-space representation of the following form (A and B are matrices) $$x_{k+1}=Ax_k+Bu_k$$
0
votes
4answers
97 views

nth term of recurrence

Im Trying to find/learn how to get the general formula for the n'th term. Im new to algebra and recurrences $$a_k = \left\{ \begin{array}{lr} 4a_{k-1} - 2a_{k-2} &: if \space k \geq 2 ...
1
vote
0answers
36 views

Linear recursions in finite fields

Let $F$ be a finite field and let $\alpha$, $\beta$ be distinct nonzero elements of $F$. Let $\alpha$ have order $r$ and let $\beta$ have order $s$. Let $M = \operatorname{lcm}(r, s)$. Let $a,b$ be ...
3
votes
3answers
38 views

Solving Recurrence Relations using Iteration

$$a_0 = 2; \qquad a_k=4a_{k-1}+5 ~ \forall\ k\ge 1$$ I have already tried solving for $a_1$ through $a_5$.
1
vote
3answers
71 views

How to apply Master theorem to this relation?

This is the definition of master theorem I am using(from Master Theorem) I am trying to use that master theorem to find the tight bound for this relation $T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$ ...
3
votes
4answers
196 views

Recurrence relation for right-angled triangles stuck-together

Given the image: and that $x_0 = 1, y_0=0$ and $\text{angles} \space θ_i , i = 1, 2, 3, · · ·$ can be arbitrarily picked. How can I derive a recurrence relationship for $x_{n+1}$ and $x_n$? I ...
0
votes
2answers
43 views

How to solve the recurrence T(n) = T(⌈n/2⌉) + 1 is O(lg n)?

How do you solve the recurrence $T(n) = T(⌈n/2⌉) + 1$ is $O(\lg n)$? In this explanation, I don't understand how the guess is made: We guess $T(n)\le c \lg(n−2)$: $$ T(n)\le c \lg(⌈n/2⌉−2)+1 \le c ...
0
votes
2answers
97 views

How to find the number of words of length n with a specific rule.

I'm given the following problem: Consider a language that uses only {1, 2, 3}. The only rule this language has is that a '3' cannot follow a '3'. How many words of length n exist in this language? ...
0
votes
1answer
33 views

Solving the nth number of this recurrence and cleaning it up using the binomial theorem.

Given this recurrence: an = an-1 – an-2 I was told to create a function that would solve for an. I thus came up with $a_n=\frac{\alpha^{n}-\beta^{n}}{i\sqrt{3}}$ Where $\alpha=\frac{1+i\sqrt{3}}{2}$...
3
votes
2answers
103 views

Solve the following recurrence relation: $S(1) = 2$; $S(n) = 2S(n-1)+n2^n, n \ge 2$

Solve the following recurrence relation: $$\begin{align} S(1) &= 2 \\ S(n) &= 2S(n-1) + n 2^n, n \ge 2 \end{align}$$ I tried expanding the relation, but could not figure out what the closed ...
2
votes
2answers
36 views

Recurrence relations help please? [closed]

How do I solve this recurrence relation? $$ a_k = a_{k-1} + k $$ when $a_0 = 2$.
2
votes
0answers
23 views

Determining asymptotics of a function given a series of difference-like inequalities

I have a function $f: \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ and I know it satisfies the following properties. $f(x) \leq \frac{\log{\sqrt{2}}}{2x}$ and for all $A \geq 1$ and $B \geq ...
0
votes
1answer
29 views

Show convergence of recursive function given different initial values

Well, I never had to show something like this which is why I'm having quite a hard time to get this one done. I basically know what I have to do but I am not capable of solving it properly. Given for ...
1
vote
1answer
58 views

Proof that mappings $K$ and $L$ are primitive recursive.

Let $J$ be the function: \begin{equation*} J(m,n)= \begin{cases} n^2+m \text { if } m\le n \\ m^2 + m + (m-n) \text { if } m > n \\ \end{cases} \end{equation*} Let $K, L$ such that $K(k)$ is ...
1
vote
0answers
21 views

Recurrence relation for the colored balls problem

Right now I am attempting to solve the recurrence thats solves a famous problem (the colored balls problem: http://mathoverflow.net/questions/41939/a-balls-and-colours-problem) given by $2i(n-i)Z_i = ...
1
vote
1answer
285 views

Find upper bound time complexity of recurrence function using iterative method

I want to find the upper bound time complexity of this function. I know how this is done using the induction method, but I can't find clear steps on how to solve it using the iteration method. <...
1
vote
1answer
45 views

Converting recurrence into matrix

How to convert $F(n) = F(n-2) + F(n-3) + 2n$ into a matrix? I am not getting how to create matrix for this?
0
votes
1answer
32 views

Solve recurrence by generating functions

Find non-recurrent expression for the following sequence: $a_0=a_1=1\;\; 5a_{n+2}=4a_{n+1}-a_n$ The formula I got for the respective generating function: $$5(A(x)-1-x)=4x(A(x)-1)-x^2A(x)$$ $$A(x)=\...
0
votes
1answer
50 views

Finding Recurrence Relation of a Search algorithm

Suppose that we have a sorted array of integers $a[0],...,a[n]$ such that $$a[i] \le a[j] \text{ for } 0 \le i \le j \le n$$ A student designs the following algorithm that searches for an ...
0
votes
2answers
84 views

Strong Induction

Define a recursive sequence $a_0$, $a_1$, $a_2$, . . . by $a_0 =1$,$a_1 =3$, $a_n$ = $2a_{n−1}$ + $8a_{n−2}$ for all integers $n≥2$ Prove by strong induction that $a_n$ $≤ 4^n$ for all integers $n ≥ ...
0
votes
1answer
86 views

Probability that a random graph is connected

Let $V=\{v_1,\dots,v_n\}$ a set of $n$ vertices. Define $\mathcal{G}$ to be the set of all graphs on $V$. $|\mathcal{G}|=2^{\binom{n}{2}}$. What is the probability that a random graph from $\mathcal{...
0
votes
1answer
37 views

Solving recurrence with moebius inversion

what's up folks? I'm solving the red book of math problems, problem 16 which is to solve the following recurrence relation: $\sum_{k=1}^n {n \choose k} a(k) = \frac{n}{n+1}$ PS: ${n \choose k} = \...
1
vote
1answer
21 views

How can we satisfy regularity condition for $T(n) = 81T(n/9) + n^4 \log n$?

Here is the question-answer It says that regularity condition is satisfied, while regularity condition is $$81\cdot \left(\frac{n^{4}\log n}{9}\right) \leq k\cdot n^4\log n$$ where $k < 1.$ So, ...