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

learn more… | top users | synonyms (2)

0
votes
1answer
49 views

Problem with Recurrence Relations

A particle P executes a random walk on the line above such that when it is at point $n$ ($1 \leq n \leq 9$, $n$ a non-negative integer), it has a probability of $0.4$ of moving to $n+1$ and a ...
7
votes
1answer
149 views

What are the solutions for $a(n)$ and $b(n)$ when $a(n+1)=a(n)b(n)$ and $b(n+1)=a(n)+b(n)$?

If you have the following recurrence relations : $a(n+1)= a(n) b(n)$ $b(n+1)= a(n) + b(n) $ How do you find the form of $a(n)$ and $b(n)$ ? I suspect there isn't a closed form , but a infinit sum ...
2
votes
0answers
38 views

How many entries in the sequence $x_n$ given by recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ are known?

The sequence $x_n$ with the recursion $x_1=1\ ,\ x_{n+1}=p_{x_n}$ , where $p_k$ denotes the $k-th$ prime, has the following values : ...
1
vote
3answers
92 views

nth element of recurrence relation

I need to find explicit equation, that will give me n-th element of this recurrence: $$ a_0=0\\ a_1=3\\ a_{n+2}=a_{n+1} + 2a_{n} $$ I know, that I can use generating functions and difference ...
1
vote
4answers
271 views

Proof the golden ratio with the limit of Fibonacci sequence [duplicate]

Let $F_n=F_{n-1}+F_{n-2}$ the Fibonacci numbers, and $\phi=\frac{1+\sqrt5}{2}$ The exercise asks me to prove that: $\lim\limits_{n \to \infty}\frac{F_{n+1}}{F_n}=\phi$. Sorry as can be proceed??
0
votes
0answers
17 views

Name of this function

Is there a name for the following function? $f(x,y) = \begin{cases} y+1, & \text{if $x=0$} \\ f(x-1,1), & \text{if $y=0$} \\ f(x-1, f(x-1,y-1)), & \text{otherwise} \end{cases}$
0
votes
0answers
25 views

Recurrence relation to calc words with odd number of letter A

I have to define the recurrence relation that allow to calc the number of words with length $n$ in the set $\{A,B,C,D,E\}$ with odd number of $A$. I almost solved it. I get to this conclusion: ...
-1
votes
1answer
53 views

A question on generating function

How to find the generating function of $\binom{2n}{n}$?
0
votes
0answers
45 views

Solving $T(n)=2T(n-1)$

I have the following recurrence relation: $$T(n)=2T(n-1)$$ I would like to find the running time of the algorithm. I tried the following, having in mind that the correct solution is $$O(2^n)$$ So ...
6
votes
1answer
52 views

The number of series over $\{0,1,2\}$ without repeating numbers

What is the number of series over $\{0,1,2\}$ with length $n$ without repeating the same number one after the other ($22$ is not allowed but $101$ is), that does not begin and end with the number $2$. ...
1
vote
0answers
45 views

How to solve nonlinear recurrence relation (quadratic)

Please help me solve this weird recurrence relation. This is not really standard quadratic, so I'm totally confused. I tried with logarithm (but 8 is excess), tried writing this recurrence in one ...
4
votes
1answer
76 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 ...
0
votes
2answers
31 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$ ...
4
votes
0answers
275 views

Series expansion for $x_n=x_{n-1}+\log \left(x_{n-1}\right)$

$x_0=2,\ x_n=x_{n-1}+\log \left(x_{n-1}\right)\quad$ has a series expansion about $1.$ Since $x_0=2,$ $(x_0-1)^k=1,$ so the recurrence can be written, up to the first $5$ terms as \begin{align} ...
0
votes
3answers
50 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
23 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 ...
2
votes
4answers
209 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
1answer
36 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 ...
0
votes
1answer
49 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 ...
1
vote
2answers
48 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
34 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 - ...
0
votes
4answers
88 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?
3
votes
2answers
45 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
43 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
15 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
38 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
39 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
36 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
28 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
44 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
15 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
55 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
56 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
26 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
30 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
30 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
53 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
12 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
32 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
25 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
46 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
75 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
19 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
16 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
19 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
95 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
26 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
39 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 ...