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

learn more… | top users | synonyms (2)

2
votes
1answer
108 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
45 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
19 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} = ...
4
votes
1answer
210 views

Duration of a Gambler's Ruin game against an opponent with infinite credit

A gambler enters the casino with $x\$$ in his pocket and sits on some table. At each iteration he bets $1\$$ and either wins $1\$$ with probability $p\leq\frac{1}{2}$ or loses $1\$$. Assuming that ...
1
vote
1answer
54 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 ...
5
votes
2answers
245 views

Method of solving no-homogeneous recurrence equation

I need to obtain a closed form of $M(t)$, satisfying the following recurrence equation: $$M(t+1)=a+bM(t)+\frac{c}{t+1}\sum_{t'=0}^tM(t')+df(t)$$ Where $f(t)$ is a known function and $a$, $b$, $c$ ...
1
vote
1answer
47 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 ...
2
votes
0answers
62 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 ...
1
vote
1answer
81 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
1answer
63 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 ...
0
votes
2answers
51 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 ...
1
vote
1answer
69 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. ...
0
votes
1answer
31 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
64 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 ...
0
votes
3answers
183 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 ...
8
votes
2answers
397 views

recurrence relation $f(n)=5f(n/2)-6f(n/4) + n$

I've been trying to solve this recurrence relation for a week, but I haven't come up with a solution. $f(n)=5f(n/2)-6f(n/4) + n$ Solve this recurrence relation for $f(1)=2$ and $f(2)=1$ At first ...
1
vote
1answer
92 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) ...
2
votes
1answer
97 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
2answers
48 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 ...
0
votes
1answer
45 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
27 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) + ...
1
vote
1answer
38 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 ...
-3
votes
1answer
53 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 ...
1
vote
1answer
40 views

How to solve the delay algebraic equation $xf(x) + \alpha f(x - {x_0}) - \alpha f(x + {x_0}) = 0$?

In the process of solving a problem, I am faced with the problem of finding a non-zero function $f:\mathbb{R} \to \mathbb{R}$ which satisfies the equation $$xf(x) + \alpha f(x - {x_0}) - \alpha f(x + ...
0
votes
1answer
21 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 ...
3
votes
2answers
95 views

Let $u_{n+3} = u_n + 2u_{n+1}$ . Show that $p$ divides $u_p$ for all $p$ prime number.

Let $(u_n)$ a sequence such that $u_0 = 3$, $u_1 = 0$, $u_2 = 4$ and $u_{n+3} = u_n + 2u_{n+1}$ Show that $p$ divides $u_p$ for all $p$ prime number. I'm really stuck on this exercise, ...
7
votes
2answers
287 views

Does anyone recognise this recursion sastisfied by the Bell numbers?

I derived a recursion $$B_n=\frac{1}{n}B_0+\frac{1}{n}\sum_{k=1}^{n-1}\left[\binom{n}{k}-(-1)^{n-k}\binom{n}{k-1}\right]B_k\tag{$*$}$$ which I know should be satisfied by the moments of the unit ...
0
votes
1answer
72 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
8answers
285 views

What Rule generates the sequence $8,8,10,12,12,14,16,16$?

What is the rule that generates the following sequence? I can not solve it. 8 8 10 12 12 14 16 16 For example: 1 3 5 7 9 11 Rule: $n+2$
1
vote
2answers
143 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
vote
1answer
47 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
38 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
3answers
71 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
1answer
26 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
1answer
42 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$, ...
1
vote
3answers
336 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
71 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
93 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 ...
0
votes
1answer
33 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
34 views
3
votes
1answer
133 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
355 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 ...
7
votes
1answer
167 views

Nonlinear inhomogeneous recurrence $f(x)^2=f(x+1)+S(x)$ to find nested radical

I want to solve the recurrence relation $$f(x)^2=f(x+1)+S(x)$$ where $S(x)$ is a given polynomial. The background is to find nested radicals expressions of the form ...
1
vote
0answers
23 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 ...
0
votes
0answers
115 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 ...
7
votes
1answer
245 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,~ ...
1
vote
1answer
45 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
61 views

Recurrence with Polynomial Coefficients of $n$

How would I solve or obtain a closed-form solution for a recurrence relation like $$a_n = f_1(n)a_{n-1} + f_2(n)a_{n-2} + ... + f_k(n)a_{n-k} + g(n)$$ where $f_1, f_2, ..., f_k, g$ are polynomials and ...
0
votes
1answer
37 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
34 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 ...