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

learn more… | top users | synonyms (2)

3
votes
2answers
43 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 ...
0
votes
1answer
42 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 ...
0
votes
0answers
12 views

Is it valid recurrence for Master Theorem? $T(n)=T(n/2)+2^n$

So in class we did the following $T(n)=T(n/2)+2^n$ -----> Case 3 $ O(2^n)$ When I read in the internet it says that I cannot apply Master Theorem if f(n) is not polynomial. So what is the true ...
2
votes
1answer
30 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
35 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 ...
1
vote
0answers
31 views

Generating Series and Recurrence Relation and Closed Form

We have the following recurrence relation: $b_n=2b_{n-1}+b_{n-2}$ and initial conditions $b_0=0, b_1=2$ I use the generating series method to solve as following: Let ...
0
votes
1answer
25 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 ...
1
vote
1answer
40 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
12 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
38 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
3answers
28 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
47 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
24 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 ...
0
votes
0answers
25 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 ...
3
votes
3answers
29 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
1answer
42 views

Solving a recurrence relation using generating functions

My recurrence relation is D(n) = D(n 􀀀- 1) + D(n - 2) + 5(n -􀀀 1); with the initial conditions D(2),D(3) being 6, 17 respectively. The generating function G(z) for the sequence D(n) is given I ...
0
votes
0answers
9 views

recurrence tree final step - binary search

Starting with the base case and recursive case run times as follows: 􏰀 t(N) = 1 , if N = 1 t(N)= 1+t(N/2) ,ifN > 1 At the end of my tree I have ...
0
votes
2answers
25 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
23 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 ...
1
vote
2answers
33 views

Recurrence relations help please? [closed]

How do I solve this recurrence relation? $$ a_k = a_{k-1} + k $$ when $a_0 = 2$.
1
vote
3answers
42 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
2answers
65 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 ...
0
votes
1answer
18 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 ...
0
votes
0answers
15 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 = ...
0
votes
2answers
16 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 ...
1
vote
1answer
70 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. ...
0
votes
1answer
24 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)$$ ...
0
votes
1answer
36 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 ...
2
votes
0answers
19 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
2answers
39 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 ≥ ...
7
votes
1answer
316 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)}] = ...
0
votes
1answer
26 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
17 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, ...
1
vote
0answers
13 views

How do we get $S(m) = S(m/2) + \lg m$ from $T(n) = T(\sqrt{n}) + \lg\lg n$?

I am confused about example we got today in class. Here is a recurrence and I am not sure how we got $S(m)=S(m/2)+(\lg m)$ $$T(n)=T(\sqrt{n}) + (\lg\lg n) $$ Let $$m =\lg n$$ $$S(m)=S(m/2)+(\lg m) ...
0
votes
0answers
13 views

Regularity condition of 3rd Case of Master Theorem. Need explanation

I do not understand how regularity expression was constructed in Wiki example for 3rd Case Master Theorem. Here is what given in Wiki Shouldn't it be $$2(\frac{n^2}{2}) \leq kn^2$$ for regularity ...
0
votes
1answer
36 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?
1
vote
0answers
26 views

Probability of winning a snooker-match

Suppose, a snokker match is best of $2n-1$, so the player who wins $n$ frames wins the match. Suppose, the probability for winning a frame is $p$ for player $1$. What is the probability ...
1
vote
2answers
53 views

Non-homogeneous recurrence relation, how to solve?

Solve the following non-homogeneous recurrenece relation: $a_1 = 0, a_2= 0, a_3=1$, and $a_n = a_{n-1}+a_{n-2} + 1$ This somehow seems familiar with the Fibonacci sequence, since $a_4$ will be $2$, ...
2
votes
3answers
48 views

Is there an analytic expression for this recursive sum? $C_n = \sum _{k=0}^{n-1}C_k C_{n-1-k}$ [closed]

Is there an analytic expression for this recursive sum ? Say , $C_n = ?$ \begin{align*} C_n =& \sum _{k=0}^{n-1}C_k C_{n-1-k} \\ =& C_0C_{n-1} + C_1C_{n-2}+\cdots+C_{n-1}C_0 \end{align*} ...
1
vote
0answers
22 views

Generating function of non-linear recursion

I'm just not able to understand how they got from where they substituted a subscript n after the second equals to sign from 5.27 to x(A(x))^2 Any help would be much appreciated.
6
votes
4answers
63 views

Proving that the elements of $A^n$ matrix are non-zero

Let $ A = \begin{pmatrix} 1 & 2 \\-1 & 1 \\ \end{pmatrix}$. Prove that for every positive integer $n$ there exist integers $x_{n},y_{n}$ such that $A^n= \begin{pmatrix} x_{n} & -2y_{n} \\ ...
0
votes
1answer
38 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 ...
0
votes
1answer
21 views

Non-linear recursion-Generating functions

How would I find the generating function in closed form of a non-linear recursion? Are there any standard tricks that can be applied to non-linear recursions to find their generating functions in ...
1
vote
1answer
35 views

Reccurence equation $f(n)=6f(n-1)-9f(n-2)+(n^2+1)3^n$

$f(n)=6f(n-1)-9f(n-2)+(n^2+1)3^n$ The root for the above relation is 3 two times. So its general term will be: $f(n) = c_{1}3^n + c_{2}n3^n + something$ According to my notes $something: ...
1
vote
1answer
42 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
3answers
34 views

Recurrence equation solution

I have the following equation that I need to solve (just find its form and replace numbers with $A,B$,... $a_{n} = 8a_{n-2} - 16a_{n-4}$ My problem is that there is no $a_{n-1} , a_{n-3}$. Do I ...
0
votes
0answers
19 views

Result of a $2D$ random walk with position dependent probabilities

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk:- A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
2
votes
1answer
45 views

Solving the recurrence relation obtained from the power series method

Assuming the solution to my differential equation is of the form $y=\sum_{n=0}^\infty a_nx^n$, I was able to get to the recurrence relation. The recurrence relation is $$a_{n+2} = \dfrac ...
1
vote
1answer
21 views

Recurrence Relation when A = 0

Find the recurrence relation for: $a_k = -4_{k-1}-4_{k-2}$ when $a_0=0$ and $a_1=1$ Step 1: $r^k=-4r^{k-1}-4r^{k-2}$ Step 2: $0= r^2+4r+4 = (r+2)^2$ $r_1=r_2=-2$ $a_k=A(r_1)^k +Bk(r_2)^k$ (when ...
1
vote
1answer
22 views

$2^n=na_n+na_{n-1}-a_{n-1}$ by range transformation

I want to range transform $2^n=na_n+na_{n-1}-a_{n-1}$ to get rid of the $2^n$ term and then solve it with any other method (seems like telescoping will work once it's reduced). I've tried ...