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

learn more… | top users | synonyms (2)

1
vote
0answers
42 views

Solve recurrence $a[n,k]=(2m-2k)\;a[n-1,k+1]+k\;a[n-1,k]$

I'm trying to count how many vectors of size $n$ there are, given that the elements of the vector are integers from the range $\{-m,m\}-\{0\}$ (zero is excluded), and there are no pair of elements ...
1
vote
0answers
66 views

May someone tell me where I went wrong when finding a closed-form solution to a recursion?

Let $r(n)=\left\lceil\frac{n}{4}\right\rceil$, where $k \in \mathbb{N}$. Note that this can be rewritten as a recursion $R(n)=R(n-4)+1$, where, $R(0)=0, R(1)=1, R(2)=1, R(3)=1$. Since this recursion ...
1
vote
1answer
116 views

What's a useful recurrence relation for $(2n)!$ in terms of $n!$?

I want to make an algorithm for $n!$ which will divide the number in half and call the algorithm again until n is so close to $0$ that a value of $1$ can be safely returned, and use the value of each ...
1
vote
0answers
46 views

Recurrence of a function

Consider the following recurrence: $$ T(n) = 2T(n/2)+n\lg n$$ Let’s use a base-case $T (2) = 2$ and let’s assume $n$ is a power of $2$. (a) “guess and prove by induction” method, considering the ...
1
vote
0answers
42 views

Algorithms: Recurrence

Here's a problem that I am struggling with... If two algorithms A and B both solve the same problem. On an input of size $n$ Algorithm $A$ breaks it into $5$ pieces of size $n/2$, recursively solves ...
1
vote
0answers
25 views

Difference equation - counting problem

I need to to define difference equation for following problem and solve that equation using generating function. Border of length 10cm is made of small bricks (10cm long) and large bricks (20cm ...
1
vote
1answer
35 views

Difference equation formula $\sum a^t = \frac{a^t}{a-1}$.

As I explain below, this question was originally posted by user YYG, but then deleted. I am reposting the question (from memory) and I will answer it myself below. Question: In Difference Equations ...
1
vote
1answer
68 views

recurrence relation related problems

I'm having some difficulties of finding the recurrence relations of; number of divisions of internal region of n sided polygon number of paths from one point to another point in an NxN grid Can ...
1
vote
1answer
65 views

Convergence of a sequence with repeated sines [duplicate]

Let $x\in(0,\pi/2)$ and $\{a_n\}_{n\in\mathbb N}$ defined recursively as follows: $$ a_0=x, \quad \text{and} \quad a_{n+1}=\sin(a_n). $$ Show that $$ \lim_{n\to\infty}{n\,a_n^2}=3. $$ Note. There is ...
1
vote
2answers
74 views

Solving a recurrence relation in 2 variables

Given this sequence $Q_1(x)=x$, $Q_{n+1}(x)={Q_n(x+1)\over Q_n(x)}$, with $n>=1$, how can I get the explicit n-th term relation? More precisely, $Q_n(x)=$ ? (when $n>=0$) I'm eager to learn a ...
1
vote
1answer
212 views

Devise recurrence formula for restricted strings over alphabet $\left\{0,1,2\right\}$.

Let $A_n$ denote set of strings over characters $\left\{0,1,2\right\}$ of length $n$ which do not contain substring $22$. Moreover let $B_n$ denote set of strings which both do not contain ...
1
vote
0answers
124 views

What is common between difference operators and recurent relations?

They say that solutions of recurrence relations are combinations of exponential functions, the series like [1 a a^2 a^3 and etc]. I know that the difference operators have a matrix like ...
1
vote
1answer
32 views

2nd order homogeneous repeated roots

$$a_{n+2}-6a_{n+1}+9a_{n}= 3^n \quad n\geq 0 \quad a_{0}=2 \quad a_{1}=3$$ Got repeated roots of 3, so $a_{n}= A\cdot3^n+b\cdot (n\cdot3^n)$ how would i calculate A+B when there is $3^n$? Edit: So ...
1
vote
0answers
40 views

finding a recurrence relation for tile covering problem [duplicate]

for $n \ge 1$ let $t_n$ be the number of ways to.cover the squares of a 2xn xheckerboard using 1x2 tiles which can be rotated (ie 2x1 tile) and 2x2 tiles. 1x2 tile comes in 5 different colors and 2x2 ...
1
vote
1answer
21 views

What does it mean for a reccurence relation to be homogeneous?

I've seen definitions (such as the one here) that state Homogeneous: All the terms have the same exponent. but others (such as this one) claim that if the equation $a_n=\alpha_1 a_{n-1}+\alpha_2 ...
1
vote
0answers
55 views

How to derive recursive equation for expected discounted utility function?

I am trying to mathematically represent expected discounted utilities when the length of a lifetime is uncertain. $V_0$ is the expected discounted utility at $t=0$ and can be represented as such: ...
1
vote
1answer
52 views

How to prove that sum given by generating function diverges for given value of $x$

I have a generating function: $A(x)=\dfrac{3-8x}{1-4x+6x^2-3x^3}$ (also I have a recurrence from which this function is built). I have to prove that sum $\sum\limits_k a_k\left(\dfrac{4}{3}\right)^k$ ...
1
vote
0answers
49 views

Help Solving a Recurrence Relation with an Inverse Term

I am having a hard time generating a characteristic polynomial for a recurrence relation I thought of the other day, $a_n = a_{n-1} + \frac1{a_{n-1}}$. I am pretty familiar solving basic recurrence ...
1
vote
0answers
24 views

An expression for 2-dimensional element as a sum of differences of elements?

For 1-dimension, it's simple. $a_{n}=a_{1}+\sum_{i=2}^{n}(a_{i}-a_{i-1})$ But what would be the corresponding identity for 2-dimension? In other words, if we put $a_{n,m}=a_{1,1}+X$ then how can ...
1
vote
0answers
256 views

Help with find recurrence relation running time.

Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. ...
1
vote
1answer
78 views

Sequence Convergence and Limits

Here is a problem I've been working on. I am stuck and wondered if you guys could shed any light. Let $a>0$ and $u_{1}>a$. Consider the sequence $(u_{n})_{n=1}^{\infty }$ defined by: $$ ...
1
vote
0answers
74 views

“Strange” plot of a difference equation

In this book about intertemporal optimization (page 33) I've found this difference equation: $x_{t+1}=ax_t \quad, \quad a>0$ The solution is: $x_t=a^t x_0$ where $x_0$ is the initial value of ...
1
vote
1answer
45 views

getting T(n) when I get bigTheta complexity from recurrence relation

I wonder how could I solve the recurrence relation when I calculate complexities. Let me explain it via an example: $T(n)=2T(n/2) +n$. Solve this recurrence relation. I know from the Master theorem ...
1
vote
2answers
160 views

Solving the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n)$

Please help me solve the recurrence $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2}\log(n) $$
1
vote
2answers
124 views

Recurrence relation with sum on $T(n) : T(2n/3 +4)$

Well, I am having trouble dealing with this: $$T(n) = T(2n/3 + 4) + \Theta(n)$$ Usually there is a $n - k$ , and not a "$+ k$" I guessed a solution of $cn$ but the calculation seems off. Any body ...
1
vote
1answer
46 views

If $T(n) = un + \sum_i T(\lfloor r_i n \rfloor) $, show that $T(n) = \Theta(n)$

Let $(r_i)_{i=1}^m$ be a sequence of positive reals such that $\sum_i r_i < 1$ and let $t$ and $u$ be positive reals. Consider the sequence $T(n)$ defined by $T(0) = t$, $T(n) = un + \sum_i ...
1
vote
0answers
104 views

substitution method for recurrence tree

If one has recurrence function - $$T(k) = 2T(k-1)+ \frac 1k$$ how can one determine the upper and lower bounds? For upper bound, I try use 'substitution method' and drew out recurrence tree, ...
1
vote
1answer
234 views

How to solve non-homogeneous recurrence relation?

The relation is $$T(n) = T(n-1)+T(n-2)-T(n-3)+1 \quad \quad (1)$$ I tried in this way but stuck at a point . Please Help $$T(n+1) = T(n)+T(n-1)-T(n-2)+1 \quad \quad (2)$$ Subtracting $(2)$ from ...
1
vote
0answers
73 views

How to solve the recurrence relation $f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$ to find a closed-form solution?

A friend of mine gave me a math problem whose answer turned out to be $$f(n) = 1 - (1 - f(n - 1) \times (1 - p)) ^ 2$$ for some fixed $p$. I'm trying to find a closed-form solution to the ...
1
vote
0answers
62 views

Closed form of an inhomogeneous non-constant recurrence relation

I try to find a closed form for the $f_k$'s (at least for $f_1$) satisfying the following recurrence relation for any fixed $n>0$: $f_0 = 0$, $f_n = 0$, and $f_k = \frac{n}{2k}(f_{k-1} + f_{k+1} + ...
1
vote
1answer
118 views

Recurrence relation with unequal division

$$T(n) = T(3n/4) + T(n/3) + n$$ Please help me solve this recurrence relation. Somehow even Akra_Bazzi method doesn't seem to work in this case
1
vote
0answers
67 views

looking for explanation behind solution for a 1st order recurrence relation.

In lecture, we covered 1st order recurrence relations and came up with a solution by inspection. I sort of see that we're finding the next term in the sequence by multiplying the initial condition by ...
1
vote
0answers
103 views

Continued fraction of $\gamma+1$ using recursion

Number $\gamma,$ the Euler-Mascheroni constant, is defined as the value of $$\gamma = \lim_{n\to\infty} \sum_{k=1}^n \frac{1}{k} - \ln(n).$$ We know that $$\lim_{n\to\infty} ...
1
vote
0answers
264 views

Recurrent relation for number of ways to get a balanced n-binary tree

In answering a question related to binary trees, I came up with the following recurrent relation: Base cases: $$ f \left (1 \right ) = 1 $$ $$ f \left (2 \right ) = 2 $$ Recurrent relations: $$ f(n) ...
1
vote
0answers
34 views

Whether recursive relationship is a different version of principle of mathematical induction?

In connection with the question I can't get satisfied with such 'so on' type logic. Is there a better way to solve it? and the responses recieved I would like to know whether ...
1
vote
0answers
61 views

Solving a recurrence involving binomials.

Does anybody know how to solve the following recurrence? Maybe with generating functions? Any hint? $t(n) = 1 + \frac{1}{2^{n-1}} \sum_{i=0}^{n-1} {n \choose i} t(i)$
1
vote
1answer
169 views

How to determine a recurrence relation and justification

A message is transmitted by a series of signals from the following 19 signals: s1, s2, ... , S19. Knowing that the signal s1 take 1 second, signal s2 to s11 take 2 seconds each and the other signals ...
1
vote
0answers
37 views

Is there any way to solve the following recurrence relation in 2-dim with different boundary conditions?

I was trying to solve the following recursion problem. It seems like because of the different nature of the boundary conditions it is getting strange although I know the solution exists. The problem ...
1
vote
2answers
161 views

Deriving the generating function of a divide and conquer type recurrence relation

I am working through Analysis of Algorithms by Sedgewick/Flajolet On problem 3.44 I am given the recurrence, and I need to come up with a generating function. I have tried the various methods in the ...
1
vote
1answer
47 views

Asymptotic Equivalence of Another Recurrence: [duplicate]

So I have the following recurrence relation: $$f(n) = f(n-1) + f(\lceil n/2\rceil)+ 1$$ I already know that: If: $$g(n) = g(n-1) + 1$$ $$g(n) = O(n)$$ If: $$g(n) = g(\lceil n/2\rceil) + 1$$ ...
1
vote
0answers
79 views

Deriving this recursive expression for Riemann Prime Counting Function?

Why does this work? $f(n,k,1)=0$ $f(n,k,j)= \frac{1}{k} - f(\lfloor\frac{n}{j}\rfloor, k+1, \lfloor\frac{n}{j}\rfloor) + f(n,k,j-1)$ Here, f(n,1,n) computes the Riemann Prime Counting Function. ...
1
vote
0answers
54 views

Simplification of differential equation when definition interval becomes small?

Assuming the following differential equation on the interval $0<x<c$ with a rational function $f(x,c)$ $$\left(\frac{d^2}{dx^2}+f(x,c)\right)y(x,c)=0,$$ what kind of simplifications (if any) ...
1
vote
0answers
110 views

Scaling for characteristic polynomial of sequence of growing matrices

This is a follow-up question to Limit of sequence of growing matrices. There I was considering a sequence of matrices defined by $$ K_L = \left[H\otimes I_{2^{L-2}}\right]\left[I_2 \otimes ...
1
vote
1answer
60 views

Solution to the recursive relation $l_{n}=b_{n-1}+\sum_{k=0}^n l_n a_n b_{n-k} $

I have the following recursive equation $$l_{n}=b_{n-1}+\sum_{k=0}^n l_k a_k b_{n-k},\ n\geq 1$$ where $b_n=1/n!,\ a_n=S_n(-1)$ where $S_n(x)=\sum_{k=0}^n \frac{x^k}{k!}\ \forall x\in \mathbb{R}$ and ...
1
vote
1answer
64 views

Find a recursive formula for the following problem

Let $a_n$ be the number of bricks in a path that is $n \geq 1$ long. We have 3 types of bricks: Blue: $2$ cm long Red: $3$ cm long Green: $1$ cm long When a blue brick can't be placed next to a ...
1
vote
2answers
36 views

Fixed points for $k_{t+1}=\sqrt{k_t}-\frac{k_t}{2}$

For the difference equation $k_{t+1}=\sqrt{k_t}-\frac{k_t}{2}$ one has to find all "fixed points" and determine whether they are locally or globally asymptotically stable. Now I'm not quite sure ...
1
vote
0answers
38 views

Difference Schemes, Accuracy and Consistency

I have the following question: Say $u_j^{n+1}=(1-2\alpha-2\beta)u^n_j+\alpha(u_{j+1}^n+u^n_{j-1})+\beta(u^n_{j+2}+u^n_{j-2})$ is a scheme for $u_t=u_{xx}$. When $\Delta t/(\Delta x)^2$ and ...
1
vote
0answers
78 views

When is it justified to approximate a difference equation with its corresponding differential equation?

Consider the difference equation $f_{x+1}-f_x=a(f_x)$ and the differential equation $g'_x=a(g_x)$. When and Why is it justified to say "$f_x - g_x = o(1) $ hence we can solve the difference equation ...
1
vote
0answers
69 views

Bounding a sequence defined recursively

Let $\{x_n\}$ be a sequence of positive numbers and $\alpha \in (0,1)$. Let $y_0 := x_n$ and $$ y_k := (\alpha \,y_{k-1} + 1-\alpha) x_{n-k} $$ for $k=1,2,\dots,n-1$. Is it possible to give a sharp ...
1
vote
2answers
40 views

Recursive formulae involving a linear operator

Given a basis $e_{1}$, $e_{2}$ in the plane, define the linear operator $F$ as $F(e_{1})=3e_{1}+e_{2}$ and $F(e_{2})=e_{2}$. Furthermore, define the sequence $u_{1},u_{2},\dots$ of vectors in the ...