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

learn more… | top users | synonyms (2)

0
votes
0answers
22 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 + Bn(-3)^n + Cn^2 (-3)^n + Dn^3 ...
1
vote
2answers
28 views

How to prove this recurrence [on hold]

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
38 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
25 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
60 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
0answers
43 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
23 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
14 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
33 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
42 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
70 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
41 views

Binary strings and recurrence relations [on hold]

How could we possibly figure this out if there are an infinite number of sequences that could be generated? Could someone please solve this problem and explain what is going on at each step? Thank you ...
2
votes
1answer
33 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
36 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
21 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
231 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
58 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
86 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
60 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$ ...
0
votes
0answers
27 views

Prove or disprove that there are no finite numbers of algorithms can solve the difference equation? [closed]

Prove or disprove that there are no finite number of algorithms can solve the all the difference equation? Please comment below regarding this problem
4
votes
0answers
68 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
26 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 ; ...
4
votes
1answer
86 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
82 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
20 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
votes
0answers
18 views

How to solve this recursive relation? [closed]

The recursive relation is $$z(t+1)=\frac{a}{z(t)}+1-a$$ $$ (t, T)\in\mathbb Z:t\geq0,t\leq T $$ If I know that $z(T)=0$, how can I use this to solve $z(t)$? Thanks a lot.
0
votes
0answers
18 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
117 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
40 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 ...
18
votes
0answers
427 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
84 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
29 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
33 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
12 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
30 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
39 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?
-2
votes
0answers
13 views

Recursive methods and master theorem

I have 3 problems which I tried doing using the master theorem, but couldn't as I found out that it is not applicable to these methods: 1) Sequential Search: T(n) = T(n-1) + O(1) 2) Selection Sort: ...
1
vote
1answer
29 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
30 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
23 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
99 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
16 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 ...