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

learn more… | top users | synonyms (2)

0
votes
0answers
17 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
24 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
1answer
16 views

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

This is the recurrence relation I am trying to solve $T(n) = 2T(\frac{n}{4}) + 16 $ $T(1) =c $ I broke down(solved this reurrence relation) to $\sqrt2*c*n + 32 * \sqrt2* n - 32$ which runs in tight ...
0
votes
0answers
21 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
33 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
0answers
26 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
37 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
27 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
10 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
20 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
35 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
33 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
40 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 ...
0
votes
0answers
24 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
19 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 ...
1
vote
0answers
8 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
39 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
64 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
32 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
31 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
22 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
2answers
62 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
25 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
43 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

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
33 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
69 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
67 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
29 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
25 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
21 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
15 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
41 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
34 views

Why do (the ranges of) these sequences intersect?

Let $\{(a_n,b_n)\}$, ($1\le n\le N$) be a finite sequence and $\{(s_n,t_n)\}$ ($n\ge 1$) be an infinite sequence, both in $(\{0\}\cup \mathbb{Z}^{+})^2$. We have $a_1=0$ and $b_N=0$. Also, either ...
0
votes
1answer
44 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 ...
1
vote
2answers
71 views

Recursively defining sets of strings discrete math

So here are the two problems: Recursively define the set of bit strings K that do not have 00 as its substring. How many bit strings of length 10 are included in the above set K? Can someone ...
-2
votes
0answers
23 views

Recursively defining sets of strings [duplicate]

So here are the two problems: Recursively define the set of bit strings K that do not have 00 as its substring. How many bit strings of length 10 are included in the above set $K$? For (1) I got ...
-1
votes
1answer
46 views

Binary strings and recurrence relations [closed]

So the problem is: How many binary strings of length n contains 111? Give a recurrence relation Tn, where Tn is the number of binary strings of length n that contains 111. How could we possibly ...
2
votes
1answer
34 views

Are these recursive sequences convergent?

Fix an integer $k > 1$. Suppose $a_1,\ldots,a_k > 0$ and for $n > k$ we define $$a_n = 1/a_{n-1} + 1/a_{n-2} + \ldots + 1/a_{n-k}$$ Are these recursive sequences always convergent for any ...
1
vote
1answer
23 views

Recurrence Relation and finding cosine of a function of them.

What if we are given $$a_{r+1}=\sqrt{\frac12(a_r+1)},r\in\{0\}\cup\mathbb N$$ How to find: $$\chi=\cos\left(\frac{\sqrt{1-a_0^2}}{\displaystyle\prod_{k=1}^{\infty}a_k}\right)$$ My try, let $a_0=1$ ...
1
vote
1answer
38 views

Why is Mergesort $O(n)$ rather than $O(n\log{n})$?

Assume we want a divide-and-conquer algorithm that finds the max and min of a set $S$ with $n = 2^k$ elements, e.g. mergesort. The recurrence for time complexity is $T(n)=2*T(n/2) +2$, for $n>2$, ...