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

learn more… | top users | synonyms (2)

5
votes
0answers
25 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. Attempt: I can evaluate the integral numerically and I have derived a method ...
3
votes
1answer
21 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 ...
0
votes
0answers
6 views

Find a recurrence relation for the number of different messages that can be sent in n microseconds

Question A :Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one stair or two stairs at a time. Question B:Messages are transmitted over ...
2
votes
1answer
27 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
18 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
24 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
12 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
27 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
28 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
53 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
38 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
23 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 ...
3
votes
4answers
96 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
18 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
41 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
34 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
21 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
25 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
36 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
votes
0answers
31 views

How can I ask a question in meta about posting some results of an analysis of certain multi-segment integer sequences? [on hold]

I have been doing some investigation using a computer program of multi-segment integer sequences. The segments are generated when you interrupt a Fibonacci-like sequence after a specified number of ...
1
vote
1answer
43 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
28 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
1answer
13 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
22 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
40 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
35 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
41 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
28 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
20 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
13 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
15 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
25 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
33 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 ...
3
votes
0answers
41 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
71 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
1answer
35 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
38 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
23 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
22 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
12 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
77 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
28 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
49 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
26 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
25 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
44 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
44 views

How to prove this recurrence [closed]

Been stuck on this problem for a good while. Not sure how to approach it any help would be great! It is problem 12.
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
35 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
77 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) ...