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

learn more… | top users | synonyms (2)

1
vote
1answer
219 views

Recursive algorithm substitution?

I'm working through a problem set through MIT's OpenCourseWare and am having some trouble with recurrences. The problem is 1-2d: Give asymptotic upper and lower bounds for $T(n)$ in each of the ...
1
vote
1answer
70 views

Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction for the sequence $x_{n+1}=x_{n} + (n+1)^3$

The sequence is described by $x_{n+1}=x_{n} + (n+1)^3$. Prove that $x_{n} = (n^{2}(n+1)^{2})/4$ via complete induction. I actually have two questions. I'm a bit lost as to how to start the induction ...
1
vote
1answer
694 views

Recurrence Relation, closed-form (linear, 2nd order, constant coeff, homogeneous)

If I have a recurrence relation, such as $h_n = h_{n-1} + 2h_{n-2}$, is there a rigid method to find a closed formula for $h_n$? As of right now, I just solve for the first few terms $h_0, h_1, h_2, ...
1
vote
2answers
472 views

Simple Maths Question - Capital Sigma/Pi

I haven't studied math in a long time and am trying to solve a simple first order non-homogeneous recurrence relation. This approach uses the general formula: $$ f(n) = \prod_{i=a+1}^n b(i) \bigg\{ ...
1
vote
1answer
60 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...
1
vote
2answers
27 views

Help resolving particular solution to recurrence relation?

$a_n=5a_{n-1} - 6_{n-2} + 4^n + 2n + 3$ for $n>=2$ , $a0 = 5, a1 = 19.$ I get the general solution $ c_n = C_12^n+C_23^n.$ For a particular solution in the form $pn = An + B + C4^n$; we have ...
1
vote
1answer
19 views

Prove that $\displaystyle\int_{x=-1}^{1}P_L(x)P_{L-1}\acute (x)\,\mathrm{d}x=\int_{x=-1}^{1}P_L\acute(x)P_{L+1} (x)\,\mathrm{d}x=0$

A question (Problem $7.4$) in my textbook (Mathematical Methods in the Physical Sciences - 3rd Edition by Mary L. Boas P578) asks me to Use $$\int_{x=-1}^{1}(P_L(x)\cdot\text{any polynomial of ...
1
vote
1answer
29 views

Closed formula for finite product series

I need to solve the recurrence: $$ \begin{align*} T(n) &= kT\left(\frac{n}{2}\right) + (k - 2)n^3 \\ &\textit{where}\; k \in \mathbb{Z}: k \geq 2 \\ &= ...
1
vote
5answers
69 views

recurrence relation unable to solve

I am trying to solve recurrence relation : $$z_n = 2z_{n-1} + z_{n-2} \;\;\;\;\;z_0=1\;\;\;z_1=3$$ Could you please help to provide a solution. I got stuck with Lamdas.. Are there some simple ...
1
vote
1answer
29 views
1
vote
1answer
40 views

Relation between two sequences or summations

Let us define two sequences \begin{equation} G_{n}=\sum_{i=1}^n a^{-i}t_{i-1} \end{equation} and \begin{equation} g_{n}=\sum_{i=1}^n t_{i-1} \end{equation} where $a$ is an integer and $t_n$ is an ...
1
vote
1answer
31 views

Limit of $13^{a_n}=12^{a_{n-1}}+5^{a_{n-2}}$

I have the following recurrence: $$13^{a_n}=12^{a_{n-1}}+5^{a_{n-2}},\;a_0=0,\;a_1=1.$$ I have to prove that it is monotone and bounded, and I have to find the limit as $n\to\infty$. It was for an ...
1
vote
3answers
30 views

Solve the linear recurrence with initial conditions $a_n=a_{n-1}+2^n+1$ and $ a_0 =0$

Let $(a_n)_{n\geq0}$ be the sequence defined by $$a_0=0\qquad\text{and}\qquad\forall n\geq0,\ a_n=a_{n-1}+2^n+1.$$ I know this is a non-homogeneous case and so far as I have gotten the general ...
1
vote
1answer
29 views

To find the Generating function for the given case

$$a_{n} = \frac{4^{3n-5}}{3^{2n+4}}$$ I was just able to reach till $a_{n}$ = ($\frac{64}{9}$) $a_{n-1}$ Don't know how to proceed further
1
vote
1answer
24 views

How to find explicit form of recurrence relation with four variables for combinatorical value

I want to know how many ways there are to choose $l$ elements in order from a set with $d$ elements, allowing repetition, such that no element appears more than $3$ times. I've thought of the ...
1
vote
1answer
22 views

Solve the recurrence relation $a_{k+2}-6a_{k+1}+9a_k=3(2^k)+7(3^k), k\geq 0, k_0=1,k_1=4.$

Solve the recurrence relation $a_{k+2}-6a_{k+1}+9a_k=3(2^k)+7(3^k), k\geq 0, k_0=1,k_1=4.$ I know that I need a general solution of the form $a_k=a^{(h)}_k+a^{(p)}_k$, where the first term is a ...
1
vote
1answer
42 views

Quadratic recurrence relation (from a math-contest)

It's given the following quadratic relation: $$a_n = \frac{a_{n-1}^2+61}{a_{n-2}}$$ Find $a_{10}$. Note that I can't use a calculator or a computer, instead I was wondering if there's a trick to find ...
1
vote
2answers
53 views

Recurrence involving derivative

I would like to get a closed form of $A_n(x)$ if verifies the following recurrence relation $$A_n(x)=\frac{d}{dx}\left(\frac{A_{n-1}(x)}{a-\cos x}\right)\,\,\,\text{and}\,\,\,A_0(x)=1.$$ Really I ...
1
vote
2answers
40 views

Solve a linear system of equation involving some recursion

$$ \begin{align*} x_{1} &= 1 + x_{2}\\ x_{2} &= 1 + \frac{1}{2} x_{3} + \frac{1}{2} x_{1}\\ &\vdots\\ x_{i} &= 1 + \frac{1}{2} x_{i+1} + \frac{1}{2} x_{1}\\ &\vdots\\ x_{n-2} ...
1
vote
1answer
43 views

Recurrence relation with blocks

We have a path of size $N$ and $1\times1$ blocks of $4$ colors: yellow, red, blue and white. We need to fill the path with blocks but we cannot have $2$ blocks of the same color in a row (we can have ...
1
vote
1answer
18 views

Inhomogeneous recurrence relation

I shall solve an inhomogeneous recurrence relation: $$x_n=2x_{n-1}+2^n,\quad x_0=2$$ My approach: The homogeneous part: $$x_n=2x_{n-1}\implies x_n-2x_{n-1}=0$$ With $x_n=x^n$ approach: ...
1
vote
1answer
35 views

Error in the CLRS book for analyzing time complexity?

4.3-8 Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/2) + n^2$ is $\Theta(n^2)$. Wouldn't it be $\Theta(n^2 \log n)$?
1
vote
1answer
36 views

How to solve this non-homogeneous recurrence?

I've made a few threads recently asking how to solve non-homogeneous recurrences and I think I've gotten the hang of it, but now I want to try a complicated thing like this: $T(n) = 4T(n-1) + 2T(n-2) ...
1
vote
1answer
32 views

Number of colorings under cyclic permutation.

Given $\lambda\vdash n$. How many ways to color $n$ beads of chaplet into $l$ colors, such that $\lambda_1$ of $1^{st}$ color, $\lambda_2$ of $2^{nd}$ color, etc. For, examples if $\lambda=(3,2)$, ...
1
vote
1answer
64 views

a nonlinear difference equation limit

let $$a_1=1, a_{n+1} = a_n + \frac{1}{a_n^2}$$, and it seems $$\lim_{n\to\infty} (a_n^3-3n-\log n) = \text{C}(constant) $$ I use computer program to verify that $$C = 1.13525585...$$,and expecting ...
1
vote
1answer
103 views

An optimal sequence of length 13

I'm looking for an optimal (or much better than I have now) increasing sequence $t_1, t_2, .., t_{13}: t_i \in N, 0 \le t_i<t_{i+1}$ where $3t_{12} + 4t_{13}$ is minimized, subject to the ...
1
vote
2answers
42 views

How to analyze the time complexity $\Theta$ of this recurrence

I am trying to understand how to show that $$T(n) = T(n/2) + T(n/4) + n^2$$ is $\Theta(n^2)$ by using a recursion tree. I tried substitution at first but it got real messy real fast. This is ...
1
vote
2answers
38 views

Finding a combinatorial recurrence relation with three variables

This question is from the generating functionology textbook, Let $f(n, m,k)$ be the number of strings of n $0$’s and $1$’s that contain exactly $m$ $1$’s, no $k$ of which are consecutive. Find a ...
1
vote
1answer
47 views

Stirling number of Second kind generating function

I would like to prove that: $$f_m(x) = \dfrac{x^m}{(1-x)(1-2x)...(1-mx)}$$ Where $$f_m(x) = \sum_{n=0}^{\infty} S(n,m)x^n$$ and $S(n,m)$ is stirling number of 2nd kind Multiplying the recurrence ...
1
vote
2answers
71 views

All the binary n-words without the sequence 011

I'm trying to find a recurrence relation for the binary words of length $n$ that don't contain the sequence $011$, my attempt is as follow: denote $f\left(n\right)$ as the number of such sequences. ...
1
vote
1answer
30 views

Finding a recurrence relation in combinatorics.

let $ S(n,k)$ be the number of options to divide $[n]$ to $k$ non-empty subsets. find $ S(n,1)$ and $ S(n,2)$. find recurrence relation for $ S(n,k)$. Ok, so my attempt was: $S(n,1)=1$ , because ...
1
vote
1answer
35 views

Exponential Generating Function Fun

Given the recurrence relation of $a_n = a_{n-1} + n$, for $n \gt 0$, Where $a_0 = 1$. I know the solution is: $a_n = \frac{1}{2}n^2 + \frac{1}{2}n + 1$. I am not having troubles finding this ...
1
vote
1answer
40 views

Symmetric random walk: mean duration given absorption occurs at 0

This is exercise 2 from Section 3.9 of Probability and Random Processes by Grimmett and Stirzaker: For a simple random walk $S$ with absorbing barriers at 0 and $N$, let $W$ be the event that the ...
1
vote
1answer
28 views

Why is the recurrence relation for finding the # of bit strings of length n that contains a pair of 2 consecutive 0's…?

$$a_n = a_{n-1} + a_{n-2} + 2^{n-2} \text{ ?}$$ The solution manual states, Let $a_n$ be the number of bit strings of length $n$ containing a pair of consecutive $O$s. In order to construct a bit ...
1
vote
1answer
18 views

Combinatorics partitioning problem: find $\sum_{n\geq 0} a_{n,k}\frac{x^n}{n!}$

'If $a_{k,n}:=$ the number of ways of partitioning $n$ distinct objects into $k$ odd parts, what is $F_k(x)=\sum_{n\geq 0} a_{n,k}\frac{x^n}{n!}=?$' If I understand correctly, $a_{k,n}$ is the $n$th ...
1
vote
1answer
28 views

What's the order class of T(n) = n(T(n−1) + n) with T(1)=1?

This recurrence basically comes from the typical solution to N-queens problem. Some people say the complexity is O(n) while giving recurrence ...
1
vote
1answer
127 views

How many binary numbers of length n do not contain the substring 000?

How many binary numbers of length $n$ do not contain the substring $000$? Denote this number by $Z_n$; find a relationship between $Z_n$, $Z_{n-1}$, and (something else not given) to form an ...
1
vote
2answers
102 views

Recurrence relation about square of Fibonacci number

Prove that the square of the Fibonacci number satisfy the recurrence relation $a_{n+3}-2a_{n+2}-2a_{n+1}+a_n = 0$, and solve this recurrence relation with the correct initial conditions.
1
vote
1answer
41 views

Formula for periodic sequence with increasing period

The first values of the sequence are: $\lt1, 0, 1, 1, 0, 0, -1, -1, -1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, -1, -1, -1, -1, -1, -1, ...
1
vote
1answer
27 views

How to solve this nonlinear difference equation $y_{t+1}-y_{t}+ty_{t+1}y_{t}=0$

I need help to solve the following difference equation: $$y_{t+1}-y_{t}+ty_{t+1}y_{t}=0$$ I start by dividing with $y_{t+1}y_{t}$. Then I get: $$y_{t}^{-1}-y_{t+1}^{-1}=-t$$ Then I assume ...
1
vote
1answer
43 views

Solving recurrence relation $a_{n+1} = \frac{3a_n^2}{a_{n-1}}$

I am currently studying recurrence relations and I am stuck at a particular problem: $$a_{n+1} = \frac{3a_n^2}{a_{n-1}}$$ for $n \geq 1$, starting with $a_0 = 1$, $a_1 = 2$. In the lecture, we only ...
1
vote
1answer
73 views

Solving a tricky recurrence relation

Given the following recurrence relation: $T_2=1$ $T_4=4$ $T_{2n}= \begin{cases} T_{2n-2}+3\bmod2n & 2T_{2n-2}\geq2n-2\\ T_{2n-2}+2\bmod2n & 2T_{2n-2} < 2n-2\\ \end{cases} ...
1
vote
1answer
69 views

Use a divide and conquer algorithm to find f(n)

Use $f(1) = a$ and $f(n) = 3f(n/2) + bn$ to show that $f(n)= a(3^m) + 2(b)(3^m) - b(2^{m+1})$. Also note that $n=2^m$ Using the recurrence relation: $f(n)= a^m (f(1)) + \sum_{i=1}^{m} ...
1
vote
1answer
52 views

Derive a ϴ(1) formula for a Recurrence relation

I'm given a piece wise function with sequence $a_0$ $a_1$ etc $$a_n = \begin{cases}8 & n=0\\-7 & n=1\\25 & n=2\\7a_{(n-2)}+6a_{n-3} & otherwise\end{cases}$$ I'm asked to derive a ...
1
vote
1answer
53 views

Solving a recurrence relation with no real roots?

$a_n - 2a_{n-1} -12a_{n-2} - 14a_{n-3} -5a_{n-4} = 0 $ I've tried a few method: setting the denominator to $1 -2x -12x^2 -14x^3 -5x^4$ and then finding the numerator by multiplying $(1 -2x -12x^2 ...
1
vote
1answer
51 views

The kth derivative of $f(x)=\log^2 x$ by induction, and the recurrence $a_k=(k-1) a_{k-1}+(k-2)!$

When I was working in my next post I've found the problem to compute the kth derivative of $f(x)=\log^2 x$, for $x>0$, Fact. If $f(x)=\log^2 x$, for $x>0$, then the kth derivative, $k\geq ...
1
vote
1answer
30 views

Solving the linear recurrence $ f(n) = f(n - 1) + 12f(n-2)$

Solve the linear recurrence: $$ f(1) = 10, f(2) = -2,\quad f(n) = f(n - 1) + 12f(n-2)$$ My solution is below. Assume: $f(n) = x^n$ $$x^n = x^{n-1} + 12x^{n-2}$$ $$x^2 = x + 12 $$ $$x^2 - x ...
1
vote
1answer
55 views

Prove by induction T(n) = T(⌊n/2⌋) +T(⌊7n/16⌋) + n

Prove by induction on n that T(n)=O(n), where T(0)=1, T(n) = T(⌊n/2⌋) +T(⌊7n/16⌋) + n So far I have, Base Case: n = 1 [1/2] + [7/16] + 1 T(1) = 1 Induction hypothesis: Assume that for arbitrary ...
1
vote
2answers
33 views

Solving Recurrence Relation with backwards substitution

I am calculating the effiency class of this R(n) = 2R(n−1)+2. with the base case of R(1) = 1 using backwards substitution. My equations came out to 4R(n-2) + 6 8R(n-3) + 14 16R(n-4) +30 I ...
1
vote
1answer
63 views

Binomial transform of Catalan numbers formula

How to prove that OEIS A007317 Binomial transform of Catalan numbers $a_{n}: 1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, .. (n = 1, 2, ..)$ has a recurrence formula: $(n+2)a_{n+2} = (6n+4)a_{n+1} - ...