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

learn more… | top users | synonyms

1
vote
1answer
218 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
1
vote
3answers
286 views

Strings and Substrings

So here is one of the last homeworks we are doing in my Discrete math class. It seems like it should be simple but I am really stuck. Any help would be greatly appreciated. Find the ordinary ...
1
vote
1answer
83 views

Convergence of $x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$

$x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$ with $x_0=a\ge0$ I calculated some values for $x_n$ with $a=0,1,2$ and recognized its monotonically decreasing (It converges to $0$). Now the standard approach ...
0
votes
1answer
22 views

Upper Bounds of Two Interdependant Recursive Sequences

For a pair of real numbers $\alpha$ and $\beta$, I need to prove that for the sequences $a_n = (-\alpha)a_{n-1} +b_{n-1}$ $b_n = (-\beta)a_{n-1}$ an upper bound exists with a form similar ...
0
votes
1answer
40 views

Master Method and use cases

$T(n)=T(n-2)+n^{2}$ and $T(n)=4T(n-2)+n^{2}$ Master method to solve these two equations? I know I can use the other cases where $a$ and $b > 0$ but since $T(n-2)$ do I assume $b$ is $1$?
0
votes
1answer
74 views

Rules Regarding Particular Solutions for Recurrence Relations

Suppose I have the recurrence relation $a_n = - a_{n-1} + a_{n-2} + 2^n + n$ Is it alright to solve for the homogeneous 'general' solution and then split the solving of the particular solution into ...
3
votes
1answer
348 views

why must orthogonal polynomials each have distinct roots?

Let $\langle\cdot,\cdot\rangle$ be any inner product on the set of functions $[a,b]\rightarrow\mathbb{R}$, and let $(p_n)_{n\in\mathbb{N}}$ be a sequence of polynomials defined by: $p_{-1}(x)=0$, ...
2
votes
5answers
239 views

Deriving Closed Form for a Recursion via Generating Functions

Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$. Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain $$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...
2
votes
2answers
73 views

Finding the coefficient in the closed form of the generating function

I try to solve the recursion $a_n=5a_{n-1}+5^n$ with $a_0=1$ with generating function, but I could not find the coefficient of $x^n$ in the closed form \begin{eqnarray*} ...
0
votes
1answer
130 views

Proof Involving Difference Operators

Let E be the forward shift operator on $x$ defined by $Ef(x) = f(x+1)$. Similarly, let $\delta$ be the forward difference operator such that $\delta f(x) = f(x+1) - f(x)$ and the inverse operator ...
2
votes
2answers
59 views

Using Generating Functions (again) to Solve Recurrences

Consider the recursion $a_n = 2a_{n-1} + (-1)^n$ where $a_0 = 2$ Then $A(x) = \sum a_n x^n$ = $2 + \sum a_n x^n$ shifting the index of summation. The only next move I can think of is to now ...
1
vote
1answer
91 views

Solving the recurrence $T(n) = T(n/2) + cn \cdot \lg \lg n - 1$

I'm trying to solve the recurrence $$ \begin{eqnarray} T(n) & = & T\left( \frac{n}{2} \right) + cn\lg \lg n - 1\\ T(2) & = & 0 \end{eqnarray} $$ where $\lg n = \log_2 n$ to get the ...
4
votes
3answers
231 views

Combinatorial Proof for a Recursive Sequence

For $n>3$ let $g_n = g_{n-1} + g_{n-3}$ where the recursion takes the value 1 for n = 0,1,2. Prove that $g_{2n} = (g_n)^2 + 2g_{n-2}g_{n-1}$ combinatorially, $n > 1$. For the time being I am ...
2
votes
2answers
127 views

Tricks to Solve Arbitrary Recursions

Consider two recursions: (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$ (2) $na_n = (n-2)a_{n-1} + n/2$ with $a_0 = 0$ When I look at the first recursion it suggests to me that I ...
12
votes
2answers
427 views

Finding the limits

Suppose $a_1=1, a_{k+1}=\sqrt{a_1+a_2+\cdots +a_k}, k \in \mathbb{N}$. Find the limits $$i)\space \lim_{n\to\infty}\displaystyle \frac{\sum_{k=1}^{n} a_{k}}{n\sqrt{n}}$$ $$ii)\space ...
1
vote
2answers
60 views

How to think about solving recurrences?

I am having trouble finding a closed-form solution to the following recurrence for $T(i)$, $0\le i\le n$. $$T(0) = T(1) + 2,\quad T(n) = 0$$ and $$T(i) = {T(i+1)\over 2} + {T(i-1)\over 2} + 1,\quad ...
4
votes
1answer
185 views

Lower bound for multivariate recurrence

I have a recurrence that looks like $$p(i,j,k) = \frac{j}{n}p(i-1,j-1,k-1) + \frac{i-j}{n}p(i-1,j,k-1)$$ $$p(i,0,k) = 1$$ $$p(i,j,0) = 0$$ $$p(0,j,k) = 0$$ The base cases are to be considered in ...
1
vote
1answer
54 views

How to find a closed formula for partial sums of recursively defined series with $t_{n} = t_{n-2} + t_{n-3}$?

If $1,1,2,2,3,4,5,7,9,12,16,21,28,37,\ldots,n$ - terms, $t_{n} = t_{n-2} + t_{n-3}$. Find the sum of such a series up to $n$ terms Progress Attempted to solve the recurrence relation $t_{n} = ...
1
vote
1answer
1k views

Solving a recurrence realtion using backward substitution.

So I've been trying my best to do this, and I have made some good progress, I just need to know if what I have done is correct and if not, what the hell am I doing wrong? :P I start off with this ...
0
votes
1answer
56 views

Recurrence into explicit formulas

Can anyone point me in the right directions for these recurrence problems? I'm having trouble figuring this out for my class I have to find the explicit formula for $H(n)$ as a fuction of $n$. ...
0
votes
1answer
408 views

Solving Recurrence Relation with Forward Substitution

I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with $$ T(n) = 4T(n/3) $$ For all $n > 1$ ...
0
votes
3answers
89 views

Recurrence relation of two next terms

For the recurrence relation, $a_{n+2}=3a_{n+1}-2a_n$ with $a_0=2$ and $a_1=3$, compute the first six terms of the sequence and derive a closed form formula for this sequence. So I'm totally lost with ...
3
votes
1answer
287 views

Finding a Linear Recurrence Relation

A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years. ...
2
votes
2answers
82 views

Recurrence Relations for $c_1$ and $c_2$

For the following recurrence relation: $a_n = 3a_{n-1}+4a_{n-2}$, where $a_0=3$ and $a_1=2$ I solved it using quadratic equation by $x^2+3x-4$. So I got to $a_n = 4^nc_1 + c_2(-1)^n$. Now to find ...
2
votes
3answers
296 views

Solving functional equation for generating function

Find the functional equation for the generating function whose coefficients satisfy $$ a_n = \sum_{i=1}^{n-1}2^ia_{n-i}, \text{ for } n\ge 2, a_0 = a_1 = 1 $$ This is what I've tried so far: $$ ...
2
votes
3answers
899 views

How do I find the closed form of a recurrence relation?

I'm stuck on how to find closed forms of recurrence relations. My current problem is: An employee joins a company in 1999 with a starting salary of $50,000. Every year this employee receives a raise ...
2
votes
2answers
78 views

Finding the expression for $q_n$

Let $q_n$ be the number of $n$-letter words consisting of letters a, b, c and d, and which contain an odd number of letters $b$. Prove that $$q_{n+1} = 2q_n + 4^n\qquad\forall n \geq 1 $$ and, ...
1
vote
2answers
70 views

Stuck on solving recurrence relation

I'm trying to find formula for the following sequence. 1, 3, 6, 10, 15... Recursive formula is pretty straightforward My attempt to solve it: Homogeneous solution Particular solution ...
2
votes
1answer
55 views

Recurrence equation question

My question (which has been edited) relates to the following recurrence relation: $$a_{j+2}=\frac{2 a_{j}}{j}$$ The book which I am reading says that the (approximate) solution is given by: ...
0
votes
3answers
61 views

Recurrence question

My question relates to the following recurrence relation: $$a_{j+2}=\frac{a_{j}}{2}$$ The book which I am reading says that the (approximate) solution is given by: $$a_{j}=\frac{C}{(j/2)!}$$ (I ...
0
votes
1answer
301 views

Recurrence Relations: general process for solving first order

So I had asked a question prior to this one about recurrence relations, but apparently it was a bad one to ask. So I'm trying again to understand how to solve these babies... Here it is: $$ ...
4
votes
1answer
88 views

Find the common limit of $\frac{2}{1/a_n+1/b_n}$ and $\sqrt{a_n b_n}$

Let $a_0=1$ and $b_0=2$, then \begin{align} a_{n+1} &= \frac{2}{\frac{1}{a_n}+\frac{1}{b_n}}, \\ b_{n+1} &= \sqrt{a_n b_n}. \end{align} The sequences $(a_n)$ and $(b_n)$ converge to the same ...
1
vote
3answers
182 views

Linear Recurrence Relations

I'm having trouble understanding the process of solving simple linear recurrence relation problems. The problem in the book is this: $$ 0=a_{n+1}-1.5a_n,\ n \ge 0 $$ What is the general process, and ...
2
votes
1answer
54 views

Finding functional equation for generating function

I'm given $$ a_n = \sum_{i=2}^{n-2} a_ia_{n-i} \quad (n\geq 3), a_0 = a_1=a_2 = 1 $$ and I need to find the functional equation for the generating function satisfying the above equality. I obtained ...
-2
votes
1answer
127 views

Showing that the Lah numbers satisfy $L(n + 1, k) = (n + k)L(n, k) + L(n, k - 1)$

Show that the Lah numbers satisfy the following recurrence relation: $$L(n + 1, k) = (n + k)L(n, k) + L(n, k - 1).$$
0
votes
1answer
208 views

Induction hypothesis when proving solution to linear homogeneous recurrence equation

I am looking at an example solution to a linear homogeneous recurrence equation of: $T(0) = 0$ $T(1) = 2$ $T(n) = 4T(n-1) - 3T(n-2), n > 1$ And solving it you get $T(n) = 3^n - 1$ In the ...
2
votes
3answers
162 views

Functional equations and generating functions

The problem asks to find the functional equations for the generating functions whose coefficients satisfy $$ a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}\,\, (n\geq1), a_0 = 1 $$ There's an example that's ...
1
vote
2answers
1k views

Need some help with this recurrence equation

I'm self studying from a book I bought to learn more about algorithms and I've been trying most of the exercises in that book, so this is not a homework. Anyways, the relation I'm trying to solve is ...
0
votes
1answer
54 views

Help creating “Halving” Equation

I am not sure if this is the correct site to ask this but here goes, I have a pseudocode for a program algorithm that I am trying to turn into an equation. Say I have a variable X. Now if X is 8, ...
5
votes
2answers
244 views

Combinatorial explanation to following recurrence relation $a_n = 2 a_{n-1} + a_{n-2}$

Question was the following: $a_n$ is the number of ternary strings (strings of 0,1,2) which contain no consecutive zeros and no consecutive ones. Find a formula for $a_n$? By brute force, I found a ...
4
votes
4answers
346 views

How to solve this recurrence relation?

There's a frog who could climb either 1 stair or 3 stairs in one shot. In how many ways he could reach at 100th stair? I came up with the solution $g(n) = g(n-3) + g(n-1)$, where $g(0)=g(1)=g(2)=1$ ...
1
vote
3answers
55 views

Simple Solutions to Homogeneous Recursions

Let $b_n - 2b_{n-2} + b_{n-3} = 0$ be a linear homogeneous recursion. I was able to solve this using a characteristic equation but deriving coefficients became incredibly messy. However, I thought ...
0
votes
1answer
131 views

Given a random sequence give a recurrence defining it.

I heard that there's some hard way to mechanically obtain a recurrence relation for a given sequence. Do you know something about it/where can I find information about it?
2
votes
1answer
140 views

Pascal Triangle Related Problem: Fibonacci Sequence on sides

I have this triangle: $$\begin{array}{} &&&&&&&1\\ &&&&&&1&&1\\ &&&&&2&&2&&2\\ ...
0
votes
3answers
598 views

Finding Particular Solutions to Non-Homogeneous Recurrence Relations

Could anyone assist me in solving the following recurrence relations? $a_n = 3a_{n-1} - 2a_{n-2} + 2^n n^2$ $b_n = -nb_{n-1} + n!$ Specifically, I am not sure how to find the particular solutions ...
3
votes
1answer
53 views

Finding Determinants Recursively

From the MIT OCW Linear Algebra (18.06) final exam, question 9: For square matrices with 3's on the diagonal, 2s on the diagonal above, and 1s on the diagonal below: $$A_1=\begin{pmatrix} 3 ...
0
votes
1answer
45 views

Split ${n\over2}\sum_{j\ge 1}2^{-j}(1-2^{-j})^{n-1}$ into oscillating terms.

Exercise 8.57 from Analysis of Algorithms (Sedgewick/Flajolet) asks for solving $p_n=2^{-n}\sum_k{n\choose k}p_k$ up to the oscillating term, for $p_0=0$ and $p_1=1$. I was able to find a functional ...
6
votes
2answers
164 views

The limit of a recurrence relation (with resistors)

Background to problem (not too important): My proposed solution: The infinitely long element, , however complex, can be represented as a single resistor of resistance $R$. Remembering the ...
3
votes
4answers
196 views

Proving that $T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)$

Show that $T(n)$ is bounded both above and below by $n$ (abusing the Big O notation) for some positive constants $c_1$ and $c_2$: $$ T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n) $$ ...
-3
votes
1answer
632 views

Find a closed form for a generating function and recurrence [closed]

Find a closed form for the generating function $R(x) = \sum_{n=0}^\infty r_nx^n$, where $r_n$ is given by the recurrence $r_n = 3r_{n-1} + 5r_{n-2} + 6n$ for $n \geq 2$ and initial conditions $r_0 = ...