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

learn more… | top users | synonyms (2)

0
votes
1answer
34 views

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves. I'm learning about recurrence relations, and I'm struggling more with defining my ...
0
votes
1answer
21 views

How to find equation for this sequence of numbers?

I have a sequence of numbers 0, 1, 5, 19, .... This is the pseudocode to generate the sequence $c = 0$ for $i=0, 1, 2, ...:$ $ c = 3c + 2^i$ Does anyone know how I would write an equation ...
1
vote
0answers
25 views

Hermite Polynomial

In a famous paper by Ait-Sahalia I have found this expression for the Hermite polynomial (pp 252, line -5): $$ H_{j+1}^{\prime}\left(z\right)=-(1+j)\,H_j(z)\quad (1) $$ where $H_j$ is the $j$-th ...
0
votes
3answers
51 views

explicit formula for $a_n$ and $b_n$ [duplicate]

Let $a_n$ and $b_n$ be natural sequence such that $$a_n+b_n\sqrt3=(1+\sqrt3)^n$$ How can I find explicit formula for $a_n$ and $b_n$
5
votes
2answers
144 views

Deducing the closed form for pentagonal numbers

Consider the sequence: $0,1,5,12,22,35,51,70,92,117,145,176,\ldots$ Find both a recurrence and a closed form for this sequence. I've done some research and found out that the majority ...
1
vote
1answer
27 views

Find a functional equation for the generating function whose coefficients satisfy the relation

Find a functional equation for the generating function whose coefficients satisfy the relation: $\qquad{}$ $a_n = 3a_{n-1} -2a_{n-2}+2, a_0=a_1=1$ When I solve this, I get the function ...
0
votes
1answer
22 views

Recurrence relations, trouble understanding the statement

I have been struggling with the English in some recurrence relations problems, since I am studying it on my own and I'm not in a combinatorial environment. Here is one in which I can't grasp what it ...
0
votes
1answer
24 views

Making a string with pieces of different length and fabric

You are making a string and have access to pieces of two different lengths, of length 1 inch and of length 2 inch. The 1 inch pieces come in 5 different fabrics and the 2 inch pieces come in 4 ...
0
votes
0answers
13 views

How to Compute Discrete Intrinsic Curvature

Given a function $f$, a region $S$ where this function is twice differentiable, and the property that all of its discrete difference series centered in $S$ converge within $S$ We have that $$ ...
1
vote
0answers
24 views

Cutting cheese into chunks [duplicate]

Into how many chunks can one cut a round piece of cheese with n straight cuts? Consider the $3D$ version My try: f(x) = number of pieces and $'x'$ as number of cuts. $f(1)=2$ $f(2)= 2 + f(1)$ ...
0
votes
1answer
25 views

Recurrence relation. Application to ternary sequences

The question is: How many ternary sequences have no double zero? For this I understand that our $n$-digit sequence either have $0,1,\dots,n$ zeroes, is this ok? If the answer of above is positive, ...
1
vote
0answers
22 views

Solve the recurrence $T(n) = T(\lfloor n/2 \rfloor)+ T(\lfloor n/3 \rfloor) + \lfloor n \log_2 n\rfloor$.

$T(0) = T(1) = T(2) = 1$. For $n \geq 3, T(n) = T(\lfloor n/2 \rfloor)+ T(\lfloor n/3 \rfloor) + \lfloor n \log_2 n\rfloor$. Express the above recursion in $O(n)$ notation. I know how to solve ...
0
votes
1answer
24 views

Solving recurrence relation $4a_n=\sum\limits_{k=1}^{n-1} a_k$

I'm trying to solve the recurrence equation $$\begin{cases}4a_n=\displaystyle\sum_{k=1}^{n-1}a_k\\[1ex]a_1=1\end{cases}$$ What I considered doing was subtracting $4a_{n-1}$ from $4a_n$: ...
0
votes
0answers
17 views

How do you find the order of a recurrence relation?

I cannot find a straight forward answer in my book or online. A lot of the answers I found are very wordy and I have trouble understanding them. For example take this recurrence relation: Is the ...
0
votes
3answers
32 views

Solve the following recurrence relations

Solve the following recurrence relations: $\qquad$a) $a_n = a_{n-1} + 3(n-1), a_0 = 1$ $\qquad$b) $a_n = a_{n-1} + 3n^2, a_0 = 10$ I know that $a_n = a_{n-1} + f(n)$ = $a_0 + \sum_{i=0}^n ...
0
votes
2answers
35 views

A question related to linear recurrence.

I have seen examples such as Towers of Hanoi and Merge Sort, which I understand but when it comes to solving this kind of problems I just don't understand where to start. If given a solution to the ...
4
votes
2answers
128 views

Prove that this system of linear equations generates $\left| \left( \begin{matrix} 1/2 \\ n \end{matrix} \right) \right|$ as a solution?

This infinite system of linear equations: $$ \begin{array}( 2x_1=1 \\ 3x_1+4x_2=2 \\ 4x_1+5x_2+6x_3=3 \\ \cdots \end{array} $$ In other words, this is particular case of a system: $$ \begin{array}( ...
1
vote
1answer
12 views

Write a recurrence relation that models how your loan balance changes from month to month.

You have saved \$40,000 for a deposit on a home purchase. A cheerful Victorian home is on sale for \$370,000. You have qualified for a home loan mortgage at an annual interest rate of 3.6% compounded ...
0
votes
1answer
47 views

How does $a_{n+1}-2a_n=2a_{n-1}$?

I'm solving non-homogeneous linear recurrences for my combinatorics class and my teacher skipped a bunch of steps in his notes, so I am trying to make sense of a particular "step" he took. We were ...
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 ...
0
votes
0answers
16 views

Asymptotic growth of $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$

Can you give a solution or a hint for finding asymptotic bound for following recurrence relation: $T(n) =T(n/3) + T(n/6) + n ^ \sqrt{\log_2n}$ I know from the source of the problem that it is ...
2
votes
1answer
70 views

What is $\lim\limits_{n \to \infty} x_n$ where $x_1=2$ and $x_{n+1}=123+\sqrt{4+5 \sin(x_n) + 6\sqrt{x_n}}$?

$$x_{n+1}=123+\sqrt{4+5 \sin(x_n) + 6\sqrt{x_n}}, \quad x_1=2$$ At first glance, this sequence seems like it will diverge, since it seems like every term is growing by at least $123$. However, I ...
0
votes
0answers
11 views

Time taken to run a function R(n,a)

R(n, a){ if n = 1 return(a); if n > 1 return (R(n − 1) + R(n − 1) + 1); } Could you please explain me why the estimated time taken to run R(n, a) as a function of n is: (2^(n−1))*(a + 1) − 1 ? ...
1
vote
0answers
31 views

Find the number of points of distance n away from origin as function of n

I came across a seemingly simple problem the other day and I thought I'd share it with anyone interested. Say you have a point in 3 dimensions. The number of points that are of distance $0$ away is ...
0
votes
1answer
31 views

Integral of Legendre Polynomial

Determine the following integral $$\int_{-1}^{1}x^{2}P_{2n-1}\left(x\right) dx$$ Using the generating function and the fact that ...
1
vote
3answers
33 views

Prove that the $c_{n}$ in $\frac{1}{1-z-z^{2}}=\displaystyle\sum_{n=0}^{\infty}c_{n}z^{z}$ satisfy a Fibonacci-like recurrence relation

I need to prove that the coefficients $c_{n}$ of the expansion $\frac{1}{1-z-z^{2}}\sum_{n=0}^{\infty}c_{n}z^{n}$ satisfy the recurrence relation $c_{0}=c_{1}=1$, $c_{n}=c_{n-1}+c_{n-2}$, by ...
1
vote
1answer
19 views

Closed form solution for generating function

The recursion formula for some probability $P_n(s)$ is $$P_{n+1}(s) = qP_n(s+1) + pP_n(s-1).$$ Define the generating function $$G(z,n) = \sum_{s=-\infty}^{\infty} z^s P_n(s)$$ and prove the ...
0
votes
1answer
22 views

How to solve this linear functional homogenous recurrence relation?

I recently came across finding eigenvalues of a particular tridiagonal matrix and trying to reduce the problem, I came to a recurrence relation, which I don't know how to solve: ...
2
votes
1answer
16 views

Closed Form Solution to Exponential Recursion

Is there a closed form solution to the function $f_n=2^{f_{n-1}}$ where $f_0=2$ ? For instance, the first few values of the function are 2, 4, 16, 65536.
0
votes
1answer
41 views

Recurrence relation for the number of ternary strings of length n that contain either two consecutive 0s or two consecutive 1s.

I'm having trouble with this one...I understand others have posted this it seems. However, I don't understand those answers/others some incorrect. I first tried thinking of the different ways this ...
0
votes
1answer
30 views

What does $[n=0]$ mean?

Namely, in the context of a recursively defined sequence: $a_n=a_{n-1}+b_{n-1}+a_{n-2}+[n=0]$ where b is an element of another sequence.
0
votes
0answers
63 views

Writing a closed polynomial from a difference table

Here is a difference table for a function $S(N)$. Your job is to fill in the table, and then write out the closed polynomial expression corresponding to $S(N)$. The third level difference row is ...
0
votes
0answers
12 views

Are these linear homogenous recurrence relations?

I'm having trouble understanding the formal definition because it is a bit wordy for me. However, the way I understood it is that to be homogenous, all the terms must have the same exponent. This is ...
0
votes
1answer
30 views

Did I solve this linear homogeneous recurrence relation correctly?

I'm not sure how to enter math on this site because I'm pretty new, but I typed my solution up on word. My solutions:
0
votes
1answer
38 views

How to solve this recurrence relation for a general $n$

We have a recurrence relation: $$a_n=1$$ $$a_{n-1}=x$$ $$a_{n-i}=xa_{n-i+1}-a_{n-i+2} $$ for $i=2,3,\ldots,n.$ How to find $a_0$ in terms of $x$? For a fixed $n$, I can solve it but it turns out ...
1
vote
2answers
26 views

How would I find the characteristic equation of this Recurrence Relation?

Find and solve a recurrence relation for the number of $n$-digit ternary sequences with no consecutive digits being equal. Since for ternary, meaning only $3$ possible entries for each space, e.g. ...
0
votes
0answers
24 views

Long-time behavior of a diffusion-like equation

I would like to known the long-time behavior of $\mathbf{u}_{t}(n)$ obeying the equation $ \mathbf{u}_{t+1}(n) = T_l\mathbf{u}_{t}(n-1) + T_0\mathbf{u}_{t}(n) + T_r\mathbf{u}_{t}(n+1) $ where $T_l = ...
0
votes
0answers
19 views

Asymptotic upper bound for recurrence relations

The question is to find asymptotic upper bound for recurrence: (1) $T(n)=(T(n/2))^2$ and (2) $T(n)=(T(\sqrt{n}))^2$ with $T(n) = \text{n for n} \leq 2$ I think I will be able to find the ...
0
votes
1answer
31 views

Asymptotic upper bound $T(n)=(T(n−1))^2$

The question is to find asymptotic upper bound for recurrence: $T(n)=(T(n−1))^2$ $T(n) = \text{n for n} \leq 2$ My attempt: I've tried to use substitution method and getting: ...
0
votes
1answer
21 views

Calculate $(\Delta^2+\Delta-2)^{-1} (n^3+1)$

Is this part correct: $$(\Delta^2+\Delta -2)^{-1} =\left( -2\left(I-\frac{\Delta^2+\Delta}{2}\right)\right)^{-1}=-\frac{1}{2} ...
0
votes
0answers
10 views

Struggling with Frobenius Solutions

$x^2y''+5xy'+(x+4)y=0$ where $y = \sum_0^\infty c_n x^{n+r}$ a - prove $x=0$ is a regular singular point (done) b - find the r's (done) c - find the solution (stuck) also, I know the r's are both ...
0
votes
1answer
26 views

Find a system of recurrence relations

Find a system of recurrence relations for the number of $n$-digit binary sequences with $k$ adjacent pairs of $1$s and no adjacent pairs of $0$s. Any help on how to go about doing this would be ...
0
votes
1answer
13 views

Prove sequence defined by recurrence relation using induction

Confused at this question, from what I gather strong induction is necessary here to prove this but the algebraic step after the Inductive Hypothesis is where I'm not too sure. Basis: 2 <= a1 = 2 ...
4
votes
0answers
174 views
+100

Is there a way to write this recurrence relation in faster-to-program manner?

I have the following recurrence relation for some coefficients $$b_{n+2} = \frac{1}{(n+3)(n+2)P_0} \sum_{k=1}^n (n-k+2) (n-k+1) b_k b_{n-k+2}, \quad n>1$$ with $b_1$ to $b_3$ and $P_0$ being the ...
-1
votes
0answers
48 views

Enumerating strings with permutations

A string of length n is called valid if it does not contain three indices $i,j,k$ such that $str[i]$$=$$str[j]$$=$$str[k]$ and $2$$*$$j$$=$$i$$+$$k$. The question is to calculate the number of valid ...
2
votes
0answers
50 views

Finding the Generating Function given a Complex Recurrence

I have the following recurrence relation: $G_0=0, G_1=1,$ $$\left(G+\frac{2}{3}\right)^n+\left(G+\frac{1+w_3}{3}\right)^n+\left(G+\frac{1+w_3^2}{3}\right)^n=0, n>1$$ where $w_3$ is the primitive ...
1
vote
1answer
33 views

Find a recurrence expression which solution have $\sin$ or $\cos$.

I, I'm a computer science student of the first course. My teacher have told us to try to find a recurrence equation for the closed-form expression: $$f(n) = 2^n + 3^n \cos\left(\frac{n\pi}{2}\right) ...
1
vote
2answers
59 views

Expansion of $(a_{{0}}+a_{{1}}x+a_{{2}}{x}^{2}+a_{{3}}{x}^{3}+\cdots)^n$

I am looking for a way to obtain the coefficient $c_k$ of $x^k$ in the expansion of $(a_{{0}}+a_{{1}}x+a_{{2}}{x}^{2}+a_{{3}}{x}^{3}+\cdots)^n$. I know it can be done by the multinomial theorem, but I ...
2
votes
0answers
15 views

Is there a formula for nested quadratic functions?

Notation: $f^{(1)} (x) = f(x) \\ f^{(n)} (x) = f\left( f^{(n-1)}(x) \right)$ I'm looking for an explicit function, $f^{(n)} (x)$, where $f(x)$ is an arbitrary degree $2$ polynomial, or a nested ...
8
votes
1answer
75 views

Newton's method for square roots 'jumps' through the continued fraction convergents

I know that Newton's method approximately doubles the number of the correct digits on each step, but I noticed that it also doubles the number of terms in the continued fraction, at least for square ...