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

learn more… | top users | synonyms (2)

0
votes
1answer
16 views

First-order Taylor series expansion

I have a first-order equation that is supposed to be solved using the Frobenius method. I am having some difficulty since the equation is not equal to zero. I would appreciate any help. y' + (1 - ...
0
votes
1answer
12 views

Find a recurrence relation for a retirement account with an initial deposit of $1000 and 3% interest per year

Given that the 3% interest per year is compounded monthly and that the person saving up adds $200 to the account each month: If for each integer ($n$) greater than 0, $A_n$ is the amount the account ...
1
vote
1answer
48 views

Solving a Recurrence Relationship

Given recurrence relationship: $g(1) = 5;\\ g(2n) = 4g(n);\\ g(2n+1) = 4g(n).$ I feel lost because of $g(2n)$ and $g(2n+1)$. Based on my coursebook, there is the common standard form, which can be ...
0
votes
0answers
37 views

Recurrence Relation; unusual exercise (For me at least)

I'm having some trouble with this reccurence problem. Usually we have just one term like $2^n$ or $3n$, but this time there one of each kind. $$\begin{align} a_{n}=5a_{n-1} - 6a_{n-2} + 2^n + 3n ...
0
votes
1answer
46 views

Solve $T(n)=16T(n/2)+2n^4$

Solve using the iteration method: $$T(n)=16T(n/2)+2n^4$$ My attempt: $$\begin{align} T(n) &=16\cdot16T(n/2^2)+2(n/2)^4+2n^4 \\ &=16\cdot16\cdot 16T(n/2^3)+2(n/2^2)+2(n/2)^4+2n^4\\ ...
0
votes
1answer
18 views

Is it possible to solve a recurrence with max()?

I have the following problem. Imagine there is a set $P=\{p_1,p_2,p_3\} \subset \mathbb Z $ and I want to describe how it changes in time. Informally, the rule is simple: At every time-step, subtract ...
0
votes
1answer
36 views

Recurrence Relation With Non-constant Coefficient

I have a question that involves finding the closed form of the generating function for this sequence $$na_n = 3a_{n-1} -4a_{n-2}+ \frac{8.3^{n-2}}{(n-2)!}$$ with $$a_0=2, a_1=6$$ My lecturer told me ...
0
votes
1answer
37 views

Can someone explain the particular solution for non homogeneous recurrence relations?

This is the recurrence relation: $a_n=5a_{n-1} - 6a_{n-2} + 4^n + 2n + 3$ for $n\geq2$ , $a_0 = 5, a_1 = 19.$ I get the general solution. $ c_n = C_12^n+C_23^n.$ The particular solution is in the ...
1
vote
2answers
30 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 ...
0
votes
1answer
46 views

How many words of length n over the alphabet {a,b,c} such that the sub-word aa does not appear?

The question asks that it be solved as a recurrence relation, as in set up a recurrence relation then determine initial values to give a solution. However I am not really confident setting up ...
4
votes
1answer
69 views

Find limit recursion of sequence $x_{n+1} = \frac{x_n+ n x_{n-1}}{n+1} $

Prove sequence $$x_{n+1} = \frac{x_n+ n x_{n-1}}{n+1} $$ $$x_0 = 0, x_1 = 1 $$ converges and find it's limit My attempt Let's prove $0 \le x_n \le 1$: $x_n \ge 0 $ (obvious) By ...
0
votes
0answers
20 views

Help with a proof of the computability of the monus function by recursion

Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) ...
3
votes
2answers
44 views

Find general formula for $a_{n+1} = \frac{a_n}{1+n a_n}$

$a_{n+1} = \frac{a_n}{1+n a_n}$ $a_0=1$ Series: $1, 1/2, 1/4, 1/7, 1/11, 1/16...$ ( we ca rewrite as $a_{n+1} = \frac{1}{\frac{1}{a_n}+n}$) By wolfram alpha answer is $\frac{2}{(n-1)^2+n+1}$ I ...
2
votes
2answers
49 views

Restrictions for rule of general sequence: $T_{n+2}=T_{n} + T_{n+1}$

This is a rule which gives a sequence where $11$ times the seventh term ($11 t_7$) is equal to the sum of the first $10$ terms ($s_{10}$), where the first two starting numbers can be chosen. Do any ...
-2
votes
1answer
88 views

How to solve given recurrence relation?

From the following recurrence relation: $a_n =- a_{n-1}+8a_{n-2}+12a_{n-3}+25\cdot3^{n-2}-18n^2+48n+14$, for $n\geq3$ Where $a_0=6, a_1 = 0 $ and $a_2=57$. My attempt: I have generated a ...
0
votes
1answer
42 views

Help with generating functions

I've got two questions. I'm trying to extract the "coefficients" of a power series. I think my terminology is incorrect here but here is what I mean. Here are some examples A(Z) = 1/(1-Z) ...
0
votes
0answers
44 views

Sum of Sequence Involving Fibonacci Sequence

I have a sequence with explicit formula $b_n = F_{n+4} -(n+3)$ The question asks me to use that formula to hence find the following sum for each $n$: $$nF_1 + (n-1)F_{2} +(n-2)F_3 +...+2F_{n-1}+F_n $$ ...
1
vote
1answer
37 views

Solving a third-order homogeneous recurrence relation with variable coefficients

I'm working on a problem that I've managed to reduce to a third-order homogeneous recurrence relation given by the following expression: $$(n + 3) f_{n + 3} - 2(n + 2) f_{n + 2} + (n - 1) f_{n + 1} + ...
1
vote
1answer
33 views

Non-homogeneous Recurrence Relation with Fibonacci Sequence

I have this question in my assignment, I'm just not sure how to handle finding the closed form fully. I have most of it. Here's the question for context. Recall that the Fibonacci sequence is defined ...
0
votes
1answer
40 views

continuous evolution

I have a discrete evolution equation such that $$\rho(t+\tau) = M_0 \rho(t)M_0^\dagger+M_1 \rho(t)M_1^\dagger$$ $M_0\;\&\;M_1$ are two operators such that $tr(M_0^\dagger M_1)=0$ i.e. they are ...
1
vote
1answer
40 views

Finding the general term

I'm having some trouble with trying to find the general term of this sequence. It has a non-linear recurrence. I would really appreciate it if anyone could help me! $ a_{n}= ...
1
vote
2answers
50 views

Find and solve simultaneous recurrence relations for determining n-digit ternary sequences whose sum of digits is a multiple of 3

I'm studying recurrence relations, and I ran into the following problem: Find and solve simultaneous recurrence relations for determining $n$-digit ternary sequences whose sum of digits is a multiple ...
4
votes
1answer
51 views

Assuming $0 \leq a_{n+1} \leq c_n a_n + b_n$ (+ other conditions), show $a_n \to 0$

In the paper "A primal-dual splitting method for convex optimization ..." (see here https://www.gipsa-lab.grenoble-inp.fr/~laurent.condat/publis/Condat-optim-JOTA-2013.pdf), Lemma 4.6 states the ...
24
votes
1answer
281 views

Is there an easy way to see that this simple recurrence is 9-periodic?

In a colloquium talk yesterday, Robert Bryant pointed out that for all initial values $a_0, a_1 \in \mathbb{R}$, the sequence generated by the recurrence relation $$ a_{n+1} = |a_n| - a_{n-1} $$ turns ...
0
votes
1answer
56 views

Recurrence proof problem

I need to show that $a_n= 2^n + a_{n-2}$ for $n$ is greater than or equal to $2$. Prior to that we are told that recursively define $a_0 = 1,\, a_1 = 3, a_2 = 5,\, $ and $ a_n = 3a_{n-2} + 2a_{n-3}$ ...
0
votes
1answer
43 views

Finding a recurrence that satisfies a sequence

Consider the sequence: $1,1,1,3,5,9,17,31,\ldots$ Find both a recurrence and a different sequence that satisfies this recurrence. Saw a decent pattern until the 31 appeared...Pretty ...
0
votes
1answer
35 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
27 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
53 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
145 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
28 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
30 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
23 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
25 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
33 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
36 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
129 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
18 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
48 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
17 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 ? ...
4
votes
1answer
94 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 ...