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

learn more… | top users | synonyms (2)

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
49 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
60 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
22 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
25 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 ...
-1
votes
0answers
38 views

How do you determine the form of the particular solution to a nonhomogeneous recurrence relation?

When solving recurrence relations of the form: $$a_n=C_1a_{n-1}+C_2a_{n-2}+F(N)$$ It is pretty well established what you should do if $F(N)$ is of the form $$n^m(\text{polynomial of order }N)s^n$$ But ...
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
28 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
55 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
20 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. ...
-2
votes
0answers
29 views

how to solve these non-homogeneous recurrence relations?

can someone tell me how to solve these recurrences plz? i know how to solve homogeneous ones but the non-homogeneous ones really confuse me. I can never work out how to guess the particular solution ...
0
votes
3answers
33 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 ...
1
vote
2answers
43 views

Combinatorics Recurrence relation

Let $h_n$ be a number sequence where $h_n = 3h_{n-1} - 2h_{n-2}$ with $h_0 = 0$ and $h_1 = 1$. Compute the ordinary generating function of $h_n$ and then using the generating function compute a ...
2
votes
1answer
43 views

Find generating functions for the Perrin and Padovan sequences

The Perrin sequence is defined by $a_0 = 3, a_1 = 0, a_2 = 2$ and $a_k = a_{k-2}+a_{k-3}$ for $k \ge 3$. The Padovan sequence is defined by $b_0 = 0, b_1=1, b_2=1$ and $b_k=b_{k-2}+b_{k-3}$ for ...
1
vote
1answer
87 views

evaluate trigonometric

To all the genius out there , here is a question about expresssing summation of hyperboilc functions : First of all, I've already proved that: $$\sinh(x + 1)- \sinh(x) = (-􀀀1 + \cosh (1)) \sinh(x) ...
5
votes
1answer
79 views

An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
1
vote
1answer
32 views

Tools for solving recurrent expresions

I've got a problem involving a recurrent expression. I would like to find a solution of $x_t$ that let me take derivatives or finding the minimum of the function. Does anybody know tools for solving ...
0
votes
1answer
29 views

Recurrance relation with non-integer part

Apologies if this has already been asked, but I'm stuck. I have a recurrance relation that I want resolve to the form $a_n=f(n,\gamma)a_0$ but I don't know what to do. The relation is: ...
1
vote
1answer
23 views

Writing a tight bound for a recurrence relation

$$\begin{align}T(n) &= 2 \cdot T(n-1) + 1\\ &= 2^2\cdot T(n-2)+2+1\\ &= 2^3\cdot T(n-3)+2^2+2+1\\ &= 2^4\cdot T(n-4)+2^3+2^2+2^1+2^0\end{align}$$ general form: $2^n\cdot T(0) + ...
0
votes
1answer
17 views

Recurrence Relation with Variable Coefficient Help

I'm sure that this question is very simple, but there are no example like it in the course material and I'm not really sure what I'm looking for online. $x_n=2^n x_{n-1}, x_0=3$ If anybody could ...
-4
votes
1answer
42 views

Edited-How can I solve polynomial recurrences like $f(n+1)=\frac{2f(n)}{f(n)+1}$

Can anybody tell me the systematic way of solving this recurrence. $$f(n+1)=\frac{2f(n)}{f(n)+1}$$ I looked over the internet, but could not find the answer. Thanks {Edit- I am sorry, previously I ...
0
votes
1answer
47 views

Mini Tetris Winning Configuration

So here's the problem: A winning configuration in the game of Mini-Tetris is a complete tiling of a 2 x n board using only the three shapes shown in Figure 1. By allowing rotations, there can be ...