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

learn more… | top users | synonyms (2)

0
votes
0answers
24 views

what will be closed form of $P_vP_{2n-v-1}-P_{v-1}P_{2n-v}?$

Let $$P_0=1,$$ $$P_1=x,$$ $$P_n(x)=xP_{n-1}-P_{n-2}.$$ For some $v∈\{1,2,…,n+1\} $, what will be closed form of $$P_vP_{2n-v-1}-P_{v-1}P_{2n-v}?$$ I want a close form like ...
-1
votes
1answer
40 views

General formula for harmonic sequence

Arithmetic sequence and arithmetic mean are correlated like that $$ a_n=\frac{a_{n-1}+a_{n+1}}{2} $$ So all elements of arithmetic sequence $a_n=a+(n-1)r$ are satisfy that. $$ ...
3
votes
3answers
43 views

Is regular selection from recurrence also recurrence?

Let $R$ be a ring, and $u=(u(0),u(1),u(2),...)$ be a sequence over $R$ ($u(i)\in R$). Let $m\ge1$, $c_0,...,c_{m-1}\in R$ be fixed elements, and the following law of recursion holds ...
0
votes
2answers
214 views

Solving the Recurrence Relation/Series fn = 1 + fn-1*(M) where M is a constant

So I'm trying to solve this week's FiveThirtyEight Riddler. In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people ...
0
votes
1answer
33 views

Use strong induction to prove that $f_n = g_n$ for all $n \in \mathbb{N}$.

I would like to use strong induction to prove that $f_n = g_n \; \forall n \in \mathbb{N}$, where $f_n$ is defined as: $f_0 = 1 \\ f_1 = 5 \\ f_2 = 10 \\ f_n = 2f_{n-1} - 4f_{n-2} \; \text{for $n ...
0
votes
0answers
17 views

Recurrence relation by substitution method

I have to find the lower and the upper bound for the following recurrence: $T(n)=\sqrt{n} T(\sqrt{n})+\sqrt{n}$ and use the substitution method. I have trouble finding out how the recursion-tree ...
0
votes
2answers
24 views

what is the value of K for given recurrence relation?

Consider the recurrence relation $a_1 = 8$, and for all $n>1$, $a_n=6n^2 + 2n+a_{n–1}$. Let $a_{99} = K\times 10000$. The value of $K$ is ___.
1
vote
2answers
28 views

Solve the recurrence $a_n=3a_{n/3}+2$ given $a_0=1$ and $n$ is a power of $3$

Solve the recurrence $$a_n=3a_{n/3}+2$$ given $a_0=1$ and $n$ is a power of $3$ I am trying to study for my final using my previous quizzes, of which I got this question wrong. My instructor wants me ...
1
vote
1answer
81 views

limit of $a_n$ when n to infinity. $a_1=\sqrt{k}$ and $a_n = \sqrt{k}^{a_{n-1}}$ . $0<k<1$.

I find a question on quora: limit of a sequence. Generalized Case 1 When you generalize this question like: \begin{align} a_1 &= \sqrt{k} \\ a_n &= \sqrt{k}^{a_{n-1}} \end{align} ...
0
votes
1answer
38 views

Given the recurrence $T_n = 2T_{n-1} - T_{n-2}$, prove by Induction that $T_n = n$

Given the recurrence$$T_n = 2T_{n-1}-T_{n-2},$$$$T_0=0$$$$T_1=1$$Prove by induction, that $T_n = n$. I have the first few steps worked out. Basis: $n = 1$$$T_1=1=n=1$$ Assume true for $n = ...
0
votes
2answers
35 views

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$

Find the sequence defined by the recurrence equation $x_{n+1} = 4x_n − x_{n−1}, (n ≥ 1)$ with $x_0 = 1$ and $x_1=2$. Find an odd prime factor of $x_{2015}$. I've found the characteristic equation to ...
1
vote
3answers
43 views

Find a close form expression for $f(x)$

Here is the problem I am currently having trouble with. I have a pretty decent basis on how to do recurrence relations, but the $\frac{1}{n!}$ has got me in a rut. I tried multiplying the right side ...
1
vote
2answers
43 views

Find the generating function for the recurrence $a_n=a_{n-1}-a_{n-2}$, with $a_0=0$ and $a_1=1.$

This was a test question and I felt confident about it but all he put on it was no and circled a problem and left it at that. My solution up until I messed up which was early was $G_a(x) = ...
0
votes
1answer
44 views

Find and solve a recurrence relation for the number of words of length n from letters A, B, C, and D

Find and solve a recurrence relation for the number of words of length $n$ from letters $A, B, C,$ and $D$ which contain at least one $A$ and the first $A$ comes before the first $B$ (if there are any ...
0
votes
2answers
19 views

How to calculate three constants in a linear recurrence problem.

Question: Verify that $x^3 - 3x^2 + 4 = (x^2 - 4x + 4)(x+1)$ And solve linear recurrence: $f(0) = 1$, $f(1) = 0$, $f(2) = 14$, $f(n) = 3 f(n-1)- 4 f(n-3)$ The characteristic equation is already ...
0
votes
0answers
6 views

Time complexity for recursion

For, this recursion, What's the time complexity? T(n) = 3T(n/2) + O(log n) I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it ...
2
votes
1answer
41 views

solve $a_n=5a_{n-1}-4a_{n-2}+3\cdot2^n$ with initial conditions $a_0=1, a_1=10$

so i am pretty sure that i have solve the homogeneous solution correctly. $a_n^h = B\cdot 4^n+C\cdot1^n$ however I am not so confident on the particular solution. Here was my attempt. Since ...
0
votes
0answers
13 views

Recurrence relation without master's theorem

$$T(n) = T(n/2) + O(n \log n).$$ I don't think I can use master's theorem because $a = 1$, $b = 1$ then $\log b a$ is $log_2(1) = 0$. And $f(n) = n\log(n)$, so $c = 1$. Then $c \ne 0$. So second form ...
0
votes
0answers
9 views

Explicit solution for a non-linear recurrence equation

Does the following non-linear recurrence equation has an explicit solution with given boundary conditions $x_0$ and $x_\infty$? $$ x_n = a + b x_{n-1}x_{n+1} $$ $a$ and $b$ are constants.
0
votes
4answers
62 views

Trying to solve recurrence $T(n)=3T(n/3) + 3$

I'm trying to solve the following recurrence without using the Master Theorem: $$T(1)=1;$$ $$T(n)=3T(n/3) + 3$$ My attempt: $T(n) = 3T(n/3) + 3$ $ = 3(3T(n/9) n/3)) + 3)$ $ = 9T(n/9) + 9$ $ = ...
2
votes
0answers
16 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 ...
0
votes
0answers
34 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
30 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
34 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) ...
1
vote
1answer
32 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
24 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
17 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
4answers
67 views

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

Please help me understand this: Solve $(x+1)y''-(2-x)y'+y =0$ First, since $x_0=0$ is an ordinary point, it can be guaranteed that we can find two independent power series solutions centered at ...
0
votes
1answer
17 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 ...
0
votes
1answer
65 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
7 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 ...
1
vote
1answer
66 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} ...
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
36 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
87 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
35 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} + ...