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

learn more… | top users | synonyms (2)

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
31 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
39 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
28 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 ...
19
votes
2answers
338 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
40 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
32 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
37 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
16 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
34 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
46 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
67 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
50 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
28 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 ...
4
votes
4answers
103 views

Solve the recurrence of the alternating sum $R_n=R_{n-1}+(-1)^{n}(n+1)^{2}$

I have been trying to solve this recurrence for a few hours, but I haven't been able to find the solution yet: $R_0=1$ $R_n=R_{n-1}+(-1)^{n}*(n+1)^{2}$. I have been trying to substitute ...
0
votes
1answer
22 views

Second order difference equation with a stochastic term

I'm trying to solve a second order difference equation. But there's a stochastic term inside the equation, I was wondering what should the correct way of approaching this problem? Here's the 2nd order ...
0
votes
1answer
45 views

Asymptotic of an interesting recurrence relation

I want to study the asymptotic behavior of the following recurrence relation: $y_1=1$; $y_{n+1}=y_n+\left(1+\frac{y_n}{n}\right)^{-n}$ for $n\ge 1$. I made an initial attempt and guessed that ...
2
votes
1answer
38 views

How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?

This is recurrence $T(n)$ $ T(n) = \begin{cases} c, & \text{if $n$ is 1} \\ 2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1} \end{cases}$ This is my attempt to show that $T(n) \in ...
0
votes
2answers
23 views

Does this recurrence relation run in $ \Theta(n) $?

This is the recurrence relation I am trying to solve: \begin{align} T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\ T(1) & = c. \end{align} I broke this down (i.e., solved this ...
0
votes
0answers
27 views

How to solve T(n) = 3T(n/4) + c

I found the pattern to this problem being the following... $$3^k T\left(\frac{n}{4^k}\right) + 3^{k-1}c + 3^{k-2}c + \cdots + c$$ I feel like this is wrong but if you can cancel common factors it ...
2
votes
2answers
37 views

Can we solve recurrence relations indexed by R?

Recurrence relations are equations with functions from $\mathbb N\rightarrow \mathbb N$. For example given $a:\mathbb N\rightarrow \mathbb N$ (write $a(n)$ as $a_n$) solving the recurrence relation ...
1
vote
1answer
66 views

Closed form for Numbers in a Triangular Array

I have a particular triangular array $$ \begin{matrix} 1 & \\ 1 & 1 \\ 1 & 2 & 3\\ 1 & 3 & 9 & 15\\ 1 & 4 & 18 & 60 & 105\\ 1 & 5 & 30 & 150 ...
0
votes
2answers
34 views

Find a recurrence relation and solve it

Let $a_n$ be the nummber of ways that 4 people can throw $n$ eyes together with a die. Every person throw once. Now I want to find a generating function and compute $a_n$ for different $n$. To do ...
0
votes
0answers
24 views

How many comparisons are needed for a binary search in a set of 64 elements

Answer: So the recurrence relation for binary search is f(n) = f(n/2) + 2. ...
0
votes
1answer
26 views

Solving Recurrence Relations with Geometric Series

If given the following problem... $$4T \left(\frac n2\right) + c$$ after getting the pattern down you see the following $$4^k T\left(\frac {n}{2^k}\right) + 3^{k-1}c + 3^{k-2} c + \cdots + 3c + c$$ ...
0
votes
3answers
44 views

How to solve recurrence relation $a_{k}=7a_{k-1}-10a_{k-2}, \forall k\ge2$ with $a_{0} = a_{1} = 2$

Unfortunately I have no idea where to even start with this. This is my first math class in almost a decade. Can anybody tell me how i would go about solving for the following recurrence relation? ...
1
vote
1answer
38 views

Directly Obtaining the $n$th Value of a Lucas Sequence

(As an aside: This question lies relatively upon the border between the realms of Computer Science and Mathematics, and thus may be appropriate for StackOverflow as well.) I am in need of a method of ...
2
votes
1answer
46 views

Solve the following recurrence relation:

Solve the following recurrence relation: $f(1) = 1$ and for $n \ge 2$, $$f(n) = n^2f(n − 1) + n(n!)^2$$ How would I go about solving this? Would I need to find a substitution $f(n) =\text{ insert ...
2
votes
1answer
26 views

Solving a linear nonhomogeneous recurrence relation with troublesome $F(n)$

I am trying to solve the following: $$a_n=5a_{n-1}-6a_{n-2}+2^n+3n$$ The general solution to the homogeneous equation is simple: $$a_n=5a_{n-1}-6a_{n-2} \rightarrow \\ r^2-5r+6=0 \rightarrow ...
2
votes
0answers
14 views

Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence

Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ...
0
votes
1answer
16 views

Recurrence Relations with Geometric Series

if we have a situation where something is like this $2^k + c(2^{k-1} + 2^{k-2} + 2^{k-3} + ... + 1)$ since in this case $r > 1$ then in Computer Science we look at $\sum_{i=1}^{n} r^{i} = ...
1
vote
1answer
29 views

Solving recurrence relations with two variables

whenever I've had to solve recurrence relations, I've kind of just messed around with it until it works. I have a more complicated case, and I was wondering if there are general strategies someone ...
1
vote
1answer
34 views

Simplified summation formula.

Suppose I have the following recursive formula: $$A(n)=-\sum_{k=0}^{n-1}\binom{n}{k}\frac{1+(-1)^{n-k}+2(n-k)(-1)^{n-k-1}}{2}A(k)$$ Then I can combine the negatives to get ...
4
votes
0answers
56 views

What is the explicit formula (solution) to this recursively defined binary matrix?

My question concerns the following binary matrix (call it matrix $A$). Or rather the entire family of such matrices, for some number of columns $n$ and rows $2^n$. The ellipses indicate that the ...
1
vote
4answers
74 views

Solution verification: Prove by induction that $a_1 = \sqrt{2} , a_{n+1} = \sqrt{2 + a_n} $ is increasing and bounded by $2$

I have the following recursive relation (sequence): \begin{align} a_1 = \sqrt{2}, \quad a_{n+1} = \sqrt{2 + a_n} \end{align} My Try: I'm a little skeptical of my manipulations near the end but it ...
2
votes
0answers
38 views

Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$ (y^2-1)^x $$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a ...
0
votes
1answer
49 views

Solve this recurrence relation

Solve the following recursions: $a_{n+1}=3a_n-a_{n-1}-1$ and $a_{n+1}=4a_n-a_{n-1}-1$. (These are to be solved separately, not simultaneously) I tried using generating functions but it got messy. Any ...
1
vote
1answer
31 views

How to prove the characteristic equation based solution of recurrence relations?

What is the proof for / where might I find the proof to: Let $c_1, c_2,..., c_k$ be real numbers. Suppose that the characteristic equation $$r^k-c_1 r^{k-1}-...-c_k=0$$ has $k$ distinct roots $r_1, ...
0
votes
2answers
23 views

Prove T(n)= T(n-2)+k is O(n) for all n >1

I'm stuck on trying to prove that $ T(n)= T(n-2)+k$ is bounded by $O(n)$ for all $n >1$ I expanded it out to reach the following guess: $T(n) = ((n-2)/2)k $ though when I try to prove ...
0
votes
0answers
21 views

Solving a non-linear homogeneous recurrence relation

I have the following non-linear homogeneous recurrence relation: $a_n = 6a_{n-1} - 12a_{n-2} + 8a_{n-3} + 2^n$ And I need to solve it by giving a general form . So I get the process. First I solve ...
2
votes
3answers
91 views

Use the generating function to solve a recurrence relation

We have the recurrence relation $\displaystyle a_n = a_{n-1} + 2(n-1)$ for $n \geq 2$, with $a_1 = 2$. Now I have to show that $\displaystyle a_n = n^2 - n +2$, with $n \geq 1$ using the generating ...
0
votes
1answer
29 views

For a solution of linear recurrence relation, $\lim_{n\to\infty}a_n^{1/n}$ is a zero of a related polynomial

On page 134 of J.H. van Lint's book A Course in Combinatorics, it says from $a_n=5a_{n-1}-7a_{n-2}+4a_{n-3}$ $(n\ge5)$, we find that $\lim_{n\to\infty}a_n^{1/n}=\theta$, where $\theta$ is the ...
0
votes
1answer
55 views

solving a recurrence without initial conditions

I have been working on this problem for two days... I can only get as the characteristic part of the recurrence, I just can't figure out a proper guess for the particular solution. ...
0
votes
3answers
34 views

Recurrence relation - equal roots of characteristic equation

I have the following problem: Solve the following recurrence relation $f(0)=3$ $f(1)=12 $ $f(n)=6f(n-1)-9f(n-2)$ We know this is a homogeneous 2nd order relation so we write the ...
0
votes
1answer
48 views

non-homogenous linear recurrence relation general questions

what happens if you have both repeated and non-repeated roots? i know there are different forms for both, so if given roots say $5, -3, -3, -3$ would it then be $A(5)^n + B(-3)^n + Cn(-3)^n + Dn^2 ...