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

learn more… | top users | synonyms (2)

2
votes
0answers
13 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
1
vote
1answer
25 views

Series with recursive terms: reciprocal of the sums of previous terms

What are some references and material that are devoted to studying series of the form $x_1+\frac1{x_1}+\frac{1}{x_1+\frac1{x_1}}+\dotsc$ where $x_1>0$ is given? For instance, my (non math) friend ...
0
votes
0answers
18 views

Multivariable recurrence: Solving $c(n,k) = c(n-1,k) + c(n-1,k-1) = \binom{n}{k}$ by algebraic methods.

Let $(c_{n,k})_{n,k=0}^{\infty}$ be defined by $c(0,0)=1$, $\:\:c(0,k)=0 \:\: \forall \: k > 0$ $$c(n,k) = c(n-1,k) + c(n-1,k-1) \:\:\: \forall \: n \geq 1$$ I can show that the ...
0
votes
0answers
25 views

Finding “equilibrium”

Say I have three amounts $A$, $B$ and $C$. And a set of conversions between them $K_{A->B}$, $K_{B->A}$ and $K_{B->C}$. The conversions denote what fraction and at what efficiency they ...
0
votes
0answers
17 views

Proving running time with induction

I need to use induction to prove the run time of the given recurrences: $T(1) = c_1$ $T(n) = T(n-1) + c_2$ Well this is the first time Im doing induction on this kind of exercise - I would like ...
0
votes
0answers
9 views

upper bound on derivatives of a function defined on an arc

Given a smooth arc on the complex plane by $z=\cos t + 0.5 i \sin t,\; t\in[\pi/10,\pi/5] $ , and a non-analytic function $f(z) = \text{Re } z $ defined on the arc. Obviously, $f(z) = g(t) ...
0
votes
3answers
28 views

Power series solution (Why the constant of the recurrence relation can be chosen arbitrarily?)

Please help me understand this: Solve $y''-xy=0$ First, since there are no singular points, it can be guaranteed that we can always find two power series independent solution, centered at $0$, and ...
0
votes
1answer
58 views

Solving a series of equations

I'm writing a piece of code to translate some data, and I keep banging my head against the wall with a one part of the transformation. I'm not as good at math as I ought to be :) Say we have a ...
0
votes
0answers
15 views

Can you identify this stochastic process?

So I run into this problem the other day and I cannot even think of the keywords I need to use to look it up. For the discrete random variable $X$ we have: $P_{\Delta X(t)} = F\big(X(t-1), ...
0
votes
1answer
13 views

Proving Recurrence Relation By Forward Substitution

I'm having trouble understanding the inductive proof of the following recurrence relation by forward substitution. I get that were plugging in the value for our induction step into the relation but I ...
1
vote
1answer
59 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
1answer
92 views

General solution of a finite-difference equation with real non-commensurable differences.

How to find a general solution of the following functional (recurrence) equation: $$f(x) = c_1 f(x - a_1) + \dots + c_n f(x - a_n), \tag{1}$$ where $c_i, a_i$, $i = 1, ... n$ are arbitrary real ...
24
votes
1answer
265 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
0answers
6 views

How to solve a difference equation with an input?

How do you solve the difference equation (initial conditions are given) $$y(k)+ay(k-1)+by(k-2)=cx(k-1)+dx(k-2)$$ where the input $x(k)=\theta(k)$ (the unit step function). I know that the general ...
0
votes
1answer
15 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 - ...
5
votes
1answer
1k views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
1
vote
1answer
46 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
1answer
10 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 ...
0
votes
2answers
25 views

Recurrence relations with multiplication

I have a recurrence relation and I am not quite sure if I am solving it correctly. The relation is this: $$t_n = 2n~t_{n-1}$$ where $t_0 = 1$ Here is how I went about solving this: First step is to ...
0
votes
1answer
26 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 ...
-2
votes
1answer
83 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
40 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
0answers
13 views

Solving recurrence relations question? [duplicate]

Hey I dont know how to do this question. Can any pls show me the working out for these question. Questions: http://pasteboard.co/uSZZRst.jpg
0
votes
1answer
16 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
0answers
27 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 ...
3
votes
4answers
947 views

expansion of $\cos^k(\theta)$

Does any body know a expansion of : $\cos^k(\theta)$ in function of $\cos$ and/or $\sin$ but without power? For example : $\cos^2(\theta)=\frac{1}{2}(\cos(2\theta)+1)$, but i would want a ...
0
votes
1answer
32 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 ...
0
votes
1answer
31 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 ...
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 ...
3
votes
1answer
66 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 ...
1
vote
1answer
26 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} + ...
0
votes
0answers
18 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) ...
0
votes
1answer
37 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 ...
2
votes
2answers
43 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 ...
1
vote
2answers
43 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 ...
0
votes
1answer
39 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
43 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 $$ ...
18
votes
3answers
361 views

Recurrence relations and limits, tough.

I would like a hint for the following, more specifically, what strategy or approach should I take to prove the following? Problem: Let $P \geq 2$ be an integer. Define the recurrence $$p_n = p_{n-1} ...
3
votes
0answers
145 views

Is there a way to write this recurrence relation in a simpler way (or a way that's faster to program)?

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
vote
1answer
31 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 ...
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
48 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
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}( ...
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 ...
0
votes
1answer
55 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
33 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
24 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$