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

learn more… | top users | synonyms (2)

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 ...
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
44 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
24 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 ...
1
vote
2answers
75 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 ...
-1
votes
1answer
49 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
36 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
25 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
39 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$, ...
0
votes
1answer
22 views

Prove that $w/w_0$ (no idle over minimum possible) $\le 2-1/n$ for any set of tasks on an n processor system

$w/w_0 $ $\le 2-1/n$ I've noticed this problem in a couple of discrete math and algorithm analysis textbooks. Many of them prove it for n=2, but I want to prove it for all n. The idea is that we ...
1
vote
3answers
257 views

Solving this recursive relation

I want to solve this recursive relation: $$i_{n+1}=4i_{n}+9$$ where the $i_1=t$ that $t \in \mathbb{N}$ I tried to make like relation about Tower of Hanoi, but no good thing happened. How can I do ...
2
votes
2answers
61 views

Solving the recursion $T(n) = T(n-1)\cdot T(n-2)$

Given $T(1) = a$ and $T(2) = b$, solve for $T(n)= T(n-1)\cdot T(n-2)$ [For the sake of clarity,that is $T(n-1)$ multiplied by $T(n-2)$ ] It was asked in one of the entrance tests for a PHD program. ...
2
votes
3answers
90 views

Proving the infinite sum of $1/2^i$ without induction

Prove $$\sum_{i=1}^n \frac{i}{2^i} = 2-\frac{n+2}{2^n} $$ Pretty trivial to do with induction, but as a practice problem for solving recurrences we have to do this only by repeating $\sum_{i=1}^n ...
1
vote
3answers
62 views

Convergence of sequence $x_{n+1}=\sqrt{2x_n+3}$

Let $f:\Bbb R \rightarrow \Bbb R$ be the function $f(x)=\sqrt{2x+3}$. (a) Show that for all $x\in[1,3], f(x)\geq x$. You may use the intermediate value theorem if you like. Let $x_0=1$ ...
4
votes
1answer
146 views

Help finding a closed form

I have the following function: $$\frac{2e^x}{e^{2x}+1+2x}=\sum_{n=0}^\infty \varepsilon_n\frac{x^n}{n!}$$ I would like to find a closed form for the $\varepsilon_k$. One thing that I do know is that ...
0
votes
1answer
29 views

Quick Recurrences Question [closed]

$$given: T(n)=4T(n/2)+n^2 ;T(1)=1\\=4[4T(n/2^2 )+(n/2)^2 ]+n^2\\=4^2 [4T(n/2^2 )+(n/2)^2 ]+n^2+n^2\\=4^3 [4T(n/2^3 )+(n/2)^2 ]+n^2/4+n^2+n^2\\…\\=4^k T(n/2^k )+$$ Here is where I'm stuck because I'm ...
0
votes
0answers
33 views

Question about Recurrences

$$given: T(n)=T(n-1)+n^3 ; ...
3
votes
1answer
108 views

How do I prove that the recurrence contains no perfect square?

Given the recurrence $$a_{n+2} = 14a_{n+1} - a_n - 6$$ with $a_1=1$ and $a_2=8$, how do I prove that none of the $a_n$'s apart from $a_1$ is a perfect square. This is not a homework problem, rather ...
2
votes
1answer
99 views

Variation of Tower of Hanoi

I have been reviewing the solution of the following problem for which I have to find a recurrence relation for the number of moves: "In the Tower of Hanoi puzzle, suppose our goal is to transfer all ...
0
votes
2answers
36 views

Solving recurrences whose characteristic equations have complex roots

In my Discrete Mathematics lecture notes, there is a section regarding solutions for linear recurrences whose characteristic polynomials have complex roots. There is a particular statement which I am ...
1
vote
0answers
22 views

function with a recurrence relation

I have this recursive equation: $$\begin{align*} F(m,n)&=F(m,n-1)+F(m-1,n)-F(m-1,n-1-m)\\\\ F(m,0)&=F\left(m,\frac12m(m+1)\right)=1\\ F(m,i)&=0\text{ if }i<0\text{ or ...
5
votes
2answers
131 views

How can I prove that this recursive sequence converges?

Let $a_0=1$, $a_1=1$ and $a_{n+2}=\frac{1}{a_{n+1}}+\frac{1}{a_n}$. How can I prove that this sequence is convergent? I know that if it's convergent, it converges to $\sqrt{2}$ and I can calculate the ...
0
votes
0answers
52 views

Counting all permutations(repeating) with no adjacent elements equal and m majority elements.

Counting all permutations(repeating) of 1 to n which have size n. 1. with no adjacent elements equal, and 2. m majority elements(A element is majority element when it appears max number of times in ...
21
votes
0answers
597 views

This one weird thing that bugs me about summation and the like

Most of us know $$\sum_{n=a}^b c_n=c_a+c_{a+1}...+c_{b-1}+c_b$$ Some of us know $$\prod_{n=a}^b c_n=c_a \cdot c_{a+1}...c_{b-1} \cdot c_{b}$$ A few of us know ...
0
votes
2answers
88 views

Solve the recurrence $T(n) = 2T(n-1)+n^2$

Solve the recurrence $$T(1) = 1, T(2) = 1, T(3) = 1,T(n) = 2T(n-1)+n^2, n > 3$$ I have now, $$T(n) = 2T(n-1)+^2 $$ $$= 2(2T(n-2)+(n-1)^2+n^2$$ $$=4T(n-2)+2(n-1)^2+n^2$$ $$....$$ ...
0
votes
1answer
30 views

Proving merge sort is $O(n^2)$ using induction

I'm trying to show that merge sort is $O(n^2)$ using induction. (I'm just concerned with powers of two for simplicity). However, I'm stuck at the last inequality Basis step: Show that there exists a ...
1
vote
0answers
21 views

Recursive definition of sequences inverse/equivalency.

So here's the problem: "Give a recursive definition of the sequence ($a_n$), $n = 1, 2, 3, ...$ if $a_n = 4n - 2$." Here's my answer:$$t_1 = 2; t_n = t_{n-1} + 4$$ However, I know this could also ...
0
votes
1answer
39 views

how to solve $ T(n) = T (2n/3) + 1$ using master theorem?

I solved the above recurrence using master theorem and applied case $2$ to solve it. However in the final answer I have $T(n) = \Theta(\log^{(k+1)} n)$ . what should happen to $k+1$? because the ...
0
votes
0answers
13 views

Complexity of recurrence containing geometic series.

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $ O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ...
0
votes
2answers
31 views

Complexity of recursive algorithm.

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time. What is the algorithms running time? Assume $ ...
1
vote
1answer
40 views

How to solve recurrence relation $T(n)=T(n-1)+\lceil \log(n) \rceil$

Without the ceilings, the solution is reasonable clear (given here). Is there a way to reach a solution with the ceilings, or the difference between the two?
1
vote
1answer
30 views

$T(n) = 4T(n/3) + n\log_3(n)$ using Mater Theorem?

I am trying to solve this recurrence using the Master Theorem. $$T(n)=4T(n/3)+n\log_3n.$$ I tried this: We have: $a=4$, $b=3$ and $f(n)=n\log_3n$. I think that $f(n)$ is $O(n^{\log_ba - ...
2
votes
0answers
33 views

Multivariable generating functions

Let's consider a 2-variable generating function for the Dyck triangle numbers. Reccurence, satisfying to the triangle conditions is $d_{n, k}=d_{n-1, k-1}+d_{n-1, k}+d_{n-1, k-1}$, $d_{0, 0}=1$, ...
0
votes
1answer
24 views

Recurrence in Kepler's Equation (trascendent equation)

Kepler's equation is $E-e\sin E = M$, where $e,M$ are constants. My teacher of celestial mechanics told me that if $e\ll 1$, I should take a first aproximation $E_1=M$, then a second aproximation ...
1
vote
1answer
33 views

recurence equation: $(\lambda + \gamma) f_n = \gamma (1-p)^{n-1} f_{n+1} + \gamma [1-(1-p)^{n-1}] f_{n+2} + \lambda f_{n-1}$

I am trying to analytically solve the following recurrence equation $(\lambda + \gamma) f_n = \gamma (1-p)^{n-1} f_{n+1} + \gamma [1-(1-p)^{n-1}] f_{n+2} + \lambda f_{n-1}\,,$ Under constraints of ...
4
votes
2answers
145 views

Optimization of parameter for recursive Cauchy sequence

I have the following recursive sequence I'm analyzing: $$V_0 = 50, V_1 = (1-10k)V_0,$$ $$V_{n+1} = (1-10k)V_n - 5kV_{n-1}$$ where $k > 0$ is a parameter that I'm investigating by running ...
0
votes
0answers
25 views

Show T(n)=T(n/5)+T(4n/5)+n/2 is $\Omega (n log n)$

I'm tasked with showing T(n)=T(n/5)+T(4n/5)+n/2 is Big-Omega n log n by drawing a recursion tree. The tree shows a lower bound with the following terms: n/2 ... n/10 ... n/50 ... etc. When I solve ...
1
vote
2answers
77 views

Solving 2nd order linear recurrence with non-constant coefficients

I am trying to find a general solution to the following definite integral: $$F_{n}{\left(a,b;z\right)}:=\int_{a}^{z}\frac{x^{n}}{\sqrt{\left(x-a\right)\left(b-x\right)}}\,\mathrm{d}x,\tag{1}$$ ...
1
vote
2answers
77 views

Solution of recursive polynomial functions

Is there anything that can be said about the roots of the polynomial $f_n(x)$ if $f_n(x) = xf_{n-1}(x) + f_{n-2}(x)$ where these are polynomials of degree $n, n-1,$ and $n-2$, respectively? My goal is ...
0
votes
0answers
20 views

Pyramidal TSP without weight

Say $G=(V,E)$ with $V=\{1,...n\}$ and $l(i,j)$ is the distance of arc $(i,j) \in E$. The aim is to find a pyramidal path in $V$ with minimal length. A pyramidal path is a sequence of vertices $(n,i_1, ...
5
votes
1answer
160 views

Complicated Multivariate Recurrence Relations For Generating Polynomials

I have the following multivariate recurrence relations all from the same system: First, suppose that $0\le k\le j\le m$, and let $N$ be an independent integer. Then we have for expressions $a(k,~ m,~ ...
0
votes
1answer
21 views

Markov-Chain with general state space - recurrent sets

I have an irreducible Markov Chain $(z_n )_{n\in \mathbb N } $ with state space $X$ and with transition-probability-kernel $K$, so $K(x,\cdot)$ is a probability measure (on the $\sigma$-Algebra ...