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

learn more… | top users | synonyms (2)

0
votes
0answers
17 views

Solve a recurrence relation using generating functions

I don't know how to solve recurrence relations using generating functions. What is the solution of $x(n)=x(n-1)+x(n-2)+4n-1$, with initial conditions $x(2)=7$ and $x(3)=19$, using generating ...
0
votes
2answers
17 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
20 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 ...
0
votes
2answers
28 views

Recurrence relations help please? [on hold]

How do I solve this recurrence relation? $$ a_k = a_{k-1} + k $$ when $a_0 = 2$.
1
vote
2answers
32 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)$ ...
-2
votes
1answer
33 views

What is this question asking me to do? [on hold]

The question is: Recurrence $T(n)=10^{\log n}$ to base $10$, show the order is $n$.
3
votes
2answers
48 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
16 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
14 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
12 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
19 views

Generating Series and Recurrence Relation

We have the following recurrence relation: $b_n=6b_{n-1}-9b_{n-2}$ and initial conditions $b_0=1, b_1=6$ I use the generating series method to solve as following: Let ...
0
votes
1answer
20 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
27 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
14 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
33 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 ≥ ...
1
vote
0answers
61 views

VERY Challenging Recurrnce 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
17 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
13 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
11 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
28 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
23 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
33 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
46 views

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

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
18 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
60 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
31 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
19 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
30 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
31 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
30 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
17 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
38 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 ...
0
votes
1answer
17 views

Proving $1+2CZ+3C^2Z^2+…=1/(1-CZ)^2$, considering $\sum\limits_{i=1}^{\infty}c^iZ^i=(1-CZ)(1+2CZ+3C^2Z^2+…)$

I'm told that we can prove this common identity for solving generating functions: $1+2CZ+3C^2Z^2+....=1/(1-CZ)^2$ Using only the property ...
0
votes
1answer
19 views

Demonstrating Strassen's method using domain transformation: $T(n)=7T(n/2)+an^2$

I want to solve the recurrence for Strassen's method (for multiplying square matrices) with domain transformation and get a closed form. The equation is given below: $T(n)=b$, at $n=2$ ...
0
votes
1answer
28 views

Getting rid of exponents with n when solving with annihilators: $a_n=a_{n-1}+2a_{n-2}+2^n+n^2$

To solve the following with annihilators: $a_n=a_{n-1}+2a_{n-2}+2^n+n^2$, for $n\ge2$, with initial conditions $a_1=0$ and $a_0=0$ we would have to get rid of the $2^n$ term at least, otherwise any ...
1
vote
1answer
28 views

Solving $\scriptsize a_n=\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+\ldots}}}$ with range transformation

This is a practice problem provided by a textbook on recurrences. Solve using range transformation: $a_n=\sqrt{a_{n-1}+\sqrt{a_{n-2}+\sqrt{a_{n-3}+...}}}$, where $a_0$ =4 The hint is to view the ...
4
votes
2answers
35 views

Solving a Recurrence Relation with a Square Root term

I've been trying to learn how to solve some recurrence relations lately and I have no idea how I would go about solving something like this, if possible. $T(n) = a \cdot T(n-1) + b \cdot ...
1
vote
3answers
33 views

Solving $a_n=5a(n/3)-6a(n/9)+2log_3n$ using domain transformation

$a_n=5a(n/3)-6a(n/9)+2log_3n$, For $n\ge9$ and n is a power of 3. $a_3=1$, and $a_1=0$ Transforming the first two terms is straightforward, but I'm not sure what to do with the log term. Should I ...
0
votes
2answers
26 views

Getting rid of $2^n$ when solving $a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ by characteristic roots

$a_n=8a_{n-1}-20a_{n-2}+16a_{n-3}+2^n$ For $n\ge3$, With initial conditions $a_2=1$, $a_1=1$, and $a_0=1$ I'd like the find the particular solution with characteristic roots. However when generating ...
0
votes
2answers
24 views

Help with Recurrence relations forward substitution and progression

I have seen a few questions regarding this topic. I have been unable to find one that could help me with analyzing the progression. My question :solve by recurrence relation using forward ...
4
votes
1answer
72 views
+50

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 ...
3
votes
1answer
32 views

Derive a closed formula for the generating function of this recurrence relation

This is a given recurrence relation $a_n=19(F_0a_{n-1}+F_1a_{n-2}+...+F_{n-1}a_0)$ where $F_n$ is Fibonacci number and $a_0=9$. Find the generating function $A(x)$ of the sequence $a_n$ I get the ...
2
votes
1answer
30 views

Tower of Hanoi variation from Concrete Mathematics - possible arrangements

From Concrete Mathematics, there is a problem that describes a variation of the Towers of Hanoi, where the disks can not move directly from peg $A$ to peg $B$, but must go through a middle peg. ...
1
vote
1answer
24 views

How to solve a generating recurrence relation with varying constant?

$$a_n = R_1a_{n-2} + R_2a_{n-3} + R_3a_{n-4} + CD^{n-4} \quad\text{ for } n\ge 4$$ I'm a little confused as to whether move the function around so that i solve the left hand side first for the ...
1
vote
0answers
31 views

Multiple Anihilating Random Walks in a Ring (cycle)

I've been trying to solve this problem for a long time. Problem Let $R$ be a cycle with $2n$ nodes and assume there are $2k$ particles performing a simple random walk in this ring (i.e., they have ...
1
vote
0answers
15 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...