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

learn more… | top users | synonyms (2)

1
vote
3answers
47 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
77 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
18 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
115 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
28 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 ...
2
votes
5answers
60 views

Prove that $a_{n+1}=a_{n} + 1/(n+1)^2$ is bounded from above

Prove that $a_{n+1}=a_{n} + 1/(n+1)^2$ is bounded from above What I have tried is $$a_n=1+1/4+\dots+1/n^2\leq 1+1+\dots +1=n$$ So I conclude that $a_n$ is bounded above by $n$. Does this ...
2
votes
0answers
22 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
47 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
374 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
32 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
17 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
14 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 ...
1
vote
1answer
43 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
36 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
77 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
58 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
33 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
64 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
48 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
32 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
37 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
51 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
35 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 ...
3
votes
1answer
224 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
64 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
22 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
25 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
18 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
29 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
35 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
44 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
32 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 ...
20
votes
2answers
397 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 ...
3
votes
1answer
53 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
46 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
47 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
20 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 ...
1
vote
1answer
38 views

Recurrence relation to closed form of generating function

I have the following recurrence relation: $$a_n=F_0a_{n-1}+F_1a_{n-2}+F_2a_{n-3}...+F_{n-1}a_0 $$ with $a_0=5$ and $F_n$ being the nth Fibonacci number. How would I find the closed form of the ...
1
vote
0answers
51 views

Degree of a Sequence of Squares Recurrence Relation

We are told that there exists a k-th order homogeneous linear recurrence relation $a_n=r_1a_{n-1}+...+r_ka_{n-k}$ which has distinct roots. We need to prove that for every $a_n$ that is satisfied by ...
2
votes
2answers
95 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
0
votes
1answer
63 views

Recurrence relation for a mortgage

Find a recurrence relation for the amount of money outstanding on a \$40,000 mortgage after n years. The interest rate on the mortgage is 10% and the yearly payment is \$2,000( the yearly payment is ...
0
votes
1answer
31 views

Rectangle tilling with smaller rectangles

To find the no of ways a rectangle of size 2 $\times $ n can be filled using 1 $\times $ 2 and 2 $\times$ 2 pieces. $$\quad$$ I tried to solve it as a recurrence relation, $a_{2 \times (n+2)} = a_{2 ...