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

learn more… | top users | synonyms (2)

0
votes
2answers
31 views

Recurrence equations with 2 or more recursive calls

How can I solve the following recurrence equation? Is there a general approach to solve rec. equation with more recursive calls? $$A(n) = 2A(n-1) + A(n-5)$$ $$A(0) = 1 , A(1) = 2,A(2) = 4, A(3) = 8, ...
-1
votes
1answer
119 views

Finding a lower bound of a function which is an inequality [closed]

A function $F(n)$ satisfies the recurrence $F(n) \le 7F(3n/2) + 3n$ for all $n \in \mathbb{N}$. Give a lower bound for $F(n)$.
0
votes
2answers
63 views

Find number of words of length n over alphabet {A, B, C} where any nonterminal A must be followed by B.

Let $a_n$ be the number of words of length n over the alphabet {A, B, C} such that any nonterminal A has to be immediately followed by B. Find $a_n$. Here's what I know: If the word starts with $C$ ...
1
vote
1answer
28 views

What's the order class of T(n) = n(T(n−1) + n) with T(1)=1?

This recurrence basically comes from the typical solution to N-queens problem. Some people say the complexity is O(n) while giving recurrence ...
2
votes
1answer
46 views

Solving a system of recurrence relations with or without generating functions

I was given the following problem: Find the closed formula that determines the number of r-digits quaternary sequences (made of 0's, 1's, 2's and 3's) in which: (i) the number of 0's is even and ...
0
votes
0answers
28 views

How to Solve this near fibbonaci Recurrence? [duplicate]

I have a recurrence that is $g_n= 4 g_{n-1} - 3 g_{n-2}$ I tried to use recursion to solve it but to no avail and I don't know how to proceed. Hope some advice can be provided.
0
votes
0answers
25 views

$x_{t+1}= 3tx_t-4x_{t-1}+1$, how can i write this equation into explicit equation?

$x_{t+1}= 3tx_t-4x_{t-1}+1$, how can i write this equation into explicit equation form?
0
votes
1answer
35 views

Create a recurrence relation for number of ways to construct something of length n

Find a recurrence relation with initial condition for number of ways to create a frieze of length n can be formed. The frieze is of width 1 and is being constructed with a supply of: -red 1x1 tiles, ...
0
votes
0answers
22 views

Recursive formula for an integral involving multiple inner products

Motivation: I am trying to form a Bayesian model where I will be performing frequent state-updates. I am seeking to find a recursive formula for a certain quantity that will enable me to perform this ...
0
votes
0answers
17 views

Not understanding how to find a particular solution for non-homogeneous recurrence

I am having alot of trouble trying to follow my textbook when they explain how to find a particular solution. I have posted the section from the book. I am not understanding what the authors mean when ...
1
vote
3answers
82 views

Find all function satisfying $f(f(n))+f(n)=2n+3k$

Find all functions $f:\mathbb{N_{0}} \rightarrow \mathbb{N_{0}}$ satisfying the equation $f(f(n))+f(n)=2n+3k,$ for all & $n\in \mathbb{N_{0}}$, where $k$ is a fixed natural number. A friend of ...
1
vote
1answer
127 views

How many binary numbers of length n do not contain the substring 000?

How many binary numbers of length $n$ do not contain the substring $000$? Denote this number by $Z_n$; find a relationship between $Z_n$, $Z_{n-1}$, and (something else not given) to form an ...
0
votes
0answers
17 views

Proving a recurrence's $\Theta$ with induction

Prove with induction that $T(n)=T(\frac n 2)+\log n = \Theta (n^2)$ Starting with the big $O$, the basis $T(2)\le c 2^2$ is obvious. Assume it's true for $n$ and prove for $n+1$: $T(n)=T(\frac n ...
0
votes
0answers
23 views

Solve a three term recursion

Consider the recursive function: $$f(a,b,c) = \frac{a}{t}(1-f(b,a-1,c)) + \frac{b}{t}f(a,b-1,c) + \frac{c}{t} f(a+1,b,c-2)$$ where $$t = a + b+c\\f(a,0,0) = 1$$ This arises in the context of game ...
1
vote
1answer
32 views

show that the equation $3z^3+(2-3ai)z^2+(6+2bi)z+4=0$has exactly one real root

show that : the equation $3z^3+(2-3ai)z^2+(6+2bi)z+4=0$ (where both $a$ and $b$ are real numbers) has exactly one real root. let $x_{1},x_{2},x_{3}$ be root,and ...
0
votes
0answers
23 views

Is masters theorem applicable here T(n) =√n T(√n)+√n?

I did my research before asking this question and this has been asked several times either on stackoverflow or mathematics stackexchange forum ...
1
vote
2answers
41 views

Finding a sequence satisfying this recurrence relation?

I just don't even know where to start with this, Find a sequence $(x_n)$ satisfying the recurrence relation: $2x_n$$_+$$_2$ = $3x_n$$_+$$_1$ + $8x_n$ + $3x_n$$_-$$_1$ Where n is a natural number and ...
1
vote
2answers
98 views

Solving the recurrence $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$ using generating functions

Solve the following recurrence using generating functions: $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$. My partial solution: We can rewrite $a_{n+2} = 3a_{n+1} - 2a_n$, as $a_{n+2} - 3a_{n+1} ...
1
vote
2answers
103 views

Recurrence relation about square of Fibonacci number

Prove that the square of the Fibonacci number satisfy the recurrence relation $a_{n+3}-2a_{n+2}-2a_{n+1}+a_n = 0$, and solve this recurrence relation with the correct initial conditions.
1
vote
1answer
41 views

Find the tight bound for the recurrence relation $T(n) = T(\frac{n}{3}) + 6^n $

$$T(1) = 2$$ $$T(n) = T(\frac{n}{3}) + 6^n \text{ For n > 1}$$ I tried using the substitution method to find it's closed form but I even from there, I could not figure out how to ...
0
votes
0answers
14 views

iterated logarithm on different arguments

So I have this recurrence which I am not able to solve using the master theorem. $r_1=\log x$ and $r_{i}=\alpha \log (2^{r_{i-1}})$ for all $i\geq 2$. I want to deteremine $r_n$ for some $n$. it ...
0
votes
1answer
34 views

Finding tight bounds to $T(n)=2T(\frac n 2) +\frac{n}{\log n}$

Find tight bounds to $T(n)=2T(\frac n 2) +\frac{n}{\log n}$ The upper bound: $\displaystyle 2T(\frac n 2) +\frac{n}{\log n} \le T(\frac n 2) +n = \sum_{i=0}^{\log n}\frac n {2^i} \le ...
2
votes
0answers
40 views

Find $\lim\limits_{n\to\infty}\frac{x_{n+1}}{x_n}! $ where $x_n=x_{n-1}+x_{n-2},x_1=1,x_2=2$

Find $\lim\limits_{n\to\infty}\frac{x_{n+1}}{x_n}! $ where $x_n=x_{n-1}+x_{n-2} ,(n>2),x_1=1,x_2=2$ $x_n=x_{n-1}+x_{n-2}$ $x_{n+1}=x_{n}+x_{n-1}$ From the first recurrence relation, ...
0
votes
0answers
37 views

Find the tight bound for the following.

Find a tight bound for the following recurrence. $$T(1) = 2$$ $$T(n) = T(\frac{n}{3}) + 4n$$ Using the master's theorem, I have: $$ 1 > \log{_3}{1}$$ $$k > \log{_b}{a}$$ Thus, I can ...
0
votes
2answers
37 views

Formula for nth term of sequence?

How do you find a formula for the nth term of the sequence defined by: $x_n$$_+$$_1$=$x_n$+2$x_n$$_-$$_1$ Where $x_0$=4 and $x_1$=-1 ? n=1,2,3,...
1
vote
1answer
37 views

Generating function for the set of $w$-free words.

Suppose $X$ is an alphabet and $w \in X^n$ is a word over it. Consider a set $P$ of $w$-free words over $X$ (a word is called $w$-free if it does not contain $w$ as a subword). I want to write a ...
1
vote
1answer
53 views

Solving a particular nonlinear recurrence relation

I am trying to solve the recurrence relation $a_{n}=\alpha a_{n-1}^2+\beta a_{n-1}$ where $\alpha$ and $\beta$ are constants. I have been trying to find specific techniques for solving this equation ...
2
votes
1answer
119 views

Solution to a recurrence relation

Set $F_k(x) := \sum_{n\geq k} S(n,k)x^n$. Prove that $$F_1(x) = \frac{x}{1-x}, \space \space \space F_2(x) = \frac{x^2}{(1-x)(1-2x)} $$ Furthermore, show that the function $F_k(x)$ satisfy the ...
2
votes
2answers
109 views

Proving recurrence relation on the cardinal of the derangements

Let $$f_n = |\{\pi \in S_n \space | \space \forall 1 \leq i \leq n : \pi(i) \neq i \}|$$ Prove that $f_1 = 0, f_2 = 1$, and $f_n = (n-1)(f_{n-1} + f_{n-2})$. Furthermore, prove that this ...
1
vote
1answer
28 views

Nonlinear recurrence relation

I have a question about solving nonlinear recurrence relation. $(a_{n+1}*a_n)^2 = \sqrt{a_n} * 2^n$ and $a_0=1$ I do not know how to solve this kind of relations. What is the strategy to solve them? ...
6
votes
1answer
91 views

How can I find $f(3)$ if $f(2x)=f^2(x)-2f(x)-\frac{1}{2}$?

If $f(2x)=f^2(x)-2f(x)-\frac{1}{2}$ and $f(1) = 2$ then find $f(3)$. Can you give me any hint that I can start with?
1
vote
0answers
25 views

Find the limiting joint distribution of $X_n$ and $X_{n-1}$ as $n \to \infty$

Let $Z_n \sim \mathcal{N}(0,1)$ and $$ X_{n+1} = \frac{1}{2} X_n - \frac{5}{16} X_{n-1} + Z_n. $$ Find the limiting joint distribution of $X_n$ and $X_{n-1}$ as $n \to \infty$. Attempt My approach ...
1
vote
1answer
50 views

Tiling a 3x1 grid with $1\times 1$ and $2\times 1$ tiles

my professor assigned as extra credit (and the due date has passed) but I'm still curious as to how I could go about doing this. Basically the goal is to find the amount of possible patterns there are ...
0
votes
1answer
20 views

Solving a double recursion relation for computing a derivative

I came across a double recursion relation I want to solve $a_{m,k}=a_{m+1,k-1}-a_{m,k-1}$ for $m,k\geq 0$. Context The first derivative of a function satisfies ...
1
vote
1answer
41 views

Formula for periodic sequence with increasing period

The first values of the sequence are: $\lt1, 0, 1, 1, 0, 0, -1, -1, -1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, ...
1
vote
2answers
24 views

Showing solutions for this recurrence relation

I am having trouble starting this question. Given that the sequence ($x_n$) satisfies the recurrence relation: $x_n$$_+$$_1$ = a$x_n$ + b$x_n$$_−$$_1$, where $n= 1, 2, ...$ and $a$ and $b$ are given ...
1
vote
1answer
37 views

System of recurrence relations with Taylor series expansion

Find $a_n,b_n$ where $a_0=1,b_0=0$ for the following relations: $a_{n+1}=2a_n+b_n$ $b_{n+1}=a_n+b_n$ Using generating functions, the system is: $f(x)-a_0=2xf(x)+xg(x)$ $g(x)-b_0=xf(x)+xg(x)$ ...
4
votes
1answer
117 views

Find $x_{2014}$ in the recurrence $x_{2n+1}=4x_n+2n+2$ and $x_{3n+2}=3x_{n+1} + 6x_{n}$

Given: $x_{2n+1}=4x_n+2n+2$ and $x_{3n+2}=3x_{n+1} + 6x_{n}$ for all $n\in\mathbb{N}$. Prove that: $x_{3n+1}=x_{n+2}-2x_{n+1}+10x_{n}$ and hence find $x_{2014}$ I am constantly failing to ...
0
votes
0answers
18 views

Nonhomogenous Recurrence Relations | p(n) for given f(n)

I've been reviewing questions for an upcoming test and I got to a question an+1 - an = 3n2 - n In the textbook I use, given f(n) = 3n2 it says to use p(n) = d2n2 + d1n + d0 and if f(n) = n to use ...
1
vote
2answers
45 views

find the solution to recurrent relation

Solving some math problem, I have faced this recurrent equation: $$S(n) = 3 S(n - 3) + 2 \sum\limits_{k = 2}^{n / 3} S(n - 3 k) \times k.$$ Here $n = 3 \alpha$, means, $n$ can be divided by $3$ ...
1
vote
2answers
55 views

Expressions for symmetric power sums in terms of lower symmetric power sums

The Newton symmetric power sums $p_k(x_1, \ldots, x_n)$, $1 \leq k \leq n$, are given by $$ p_k(x_1, \ldots, x_n) = \sum_{i=1}^n x_i^k. $$ Do you know if it's possible to express $p_k$ in terms of ...
0
votes
0answers
28 views

Solving $T(n)=T(n-1)+\log n$ with repeated substitution

Solve $T(n)=T(n-1)+\log n, T(1)=1$ using repeated substitution. Substituting back, we have: $T(n) = T(n-i) + log(n-i+1) +... + \log(n-1)+\log(n)$ And for which $i$ we have $n-i=1$? that is ...
0
votes
1answer
19 views

Recurrence Relations; partitions of a set

Need help trying to solve this problem. Let $S$ be a set of $2n$ elements and let $P_n$ represent the number of Partitions of $S$ into $n$ parts, with two elements in each part. Explain why ...
2
votes
0answers
56 views

A recursively defined sequence and a limit

Fix real numbers $ a_0 $, $ a_1 $ and define, $$ a_{n+1} = a_n + \Big(\frac{2}{n+1} \Big) a_{n-1} \space \space \forall \space n \ge 1 $$ Show that the sequence $ \Big\{ \dfrac{a_n}{n^2} ...
1
vote
1answer
36 views

How to prove asymptotic solution for recurrence equation: $T(n) = 2T(n/4)+4T(n/8) + n$ for $n>8$ with $T(n) = 1$ for $1 \leq n \leq 8$?

As title says, how does one solve $T(n) = 2T(n/4)+4T(n/8)+n$ for $n>8$ with $T(n)=1$ when $1 \leq n \leq 8$?
1
vote
0answers
23 views

Akra-Bazzi method - constructive proof

As I was familiarizing myself with different methods of computing complexities of recurrences, I stumbled upon the Akra-Bazzi method. Seeing such a beautiful result literally made my day. I was able ...
1
vote
0answers
37 views

solving a two variable recurrence

i have the following two variable recurrence: $$f(i,n+1) = f(i-1,n)*\frac{n-i+1}{n} + f(i,n)*\frac{i}{n}$$ $$f(0,n) = (\frac{1}{n})^{n-2}$$ $$f(i,0) = 0$$ I'm not sure which method can I try to ...
0
votes
1answer
35 views

finding number of subsets so that there are no two consecutive numbers in them

I already had a look at the following problem: For a given set $\{1, \dots, n\}$, how many sets are there so that there are no two consecutive numbers in them? The answer could be found by using ...
1
vote
1answer
27 views

How to solve this nonlinear difference equation $y_{t+1}-y_{t}+ty_{t+1}y_{t}=0$

I need help to solve the following difference equation: $$y_{t+1}-y_{t}+ty_{t+1}y_{t}=0$$ I start by dividing with $y_{t+1}y_{t}$. Then I get: $$y_{t}^{-1}-y_{t+1}^{-1}=-t$$ Then I assume ...
2
votes
3answers
126 views

Evaluating an infinite sum involving possibly hypergeometric terms

I was considering the following infinite sum $$ A(n) = \sum_{k=2}^{\infty}\left[\frac{(-1)^{k+n-1}}{k^n}(0k -1)(k-1)(2k-1)...((n-1)k-1) \right] $$ Some cases: $$ A(1) = ...