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

learn more… | top users | synonyms (2)

0
votes
0answers
15 views

Is this a type of recurrence relation

Consider a series of integers $a$ defined by: $$\begin{cases} a_n & = c_n & \text{if $0 \le n \le 2$} \\ a_{2n} & = f(a_n, a_{n+1}) & \text{if $n > 1$} \quad \...
9
votes
1answer
71 views

A pair of sequences defined by mutual addition/multiplication

Define sequences $\{a_n\},\,\{b_n\}$ by mutual recurrence relations: $$a_0=b_0=1,\quad a_{n+1}=a_n+b_n,\quad b_{n+1}=a_n\cdot b_n.\tag1$$ The sequence $\{a_n\}$ begins: $$1,\,2,\,3,\,5,\,11,\,41,\,371,...
-1
votes
0answers
14 views

recursive definition for two mutually exclusive events

How do we write recursive definitions for two mutually exclusive events ? Can anyone explain with some examples as how do we come up with solutions in case of exclusive events ? SO finally i add ...
1
vote
1answer
50 views

Factories processing jobs

We have two factories that can process jobs; each job takes two days to complete. The factories agree on a minimum threshold $a\in[0,1]$ to accept jobs. Every day, a value $v\in[0,1]$ is drawn ...
5
votes
1answer
57 views

Deriving sum of powers formula using generating functions

Just for fun I wanted to try to derive a formula for the sum of $p$-powers using generating functions, but without using any literature or websites for help. However I do need a small push or hint. ...
1
vote
2answers
56 views

Generating function for $\sum_{n=0}^{\infty} n^{p} x^n$

I am trying to derive the generating function for $H(x,p) = \sum_{n=0}^{\infty} n^p x^n$ I am trying to solve it with the following logic: (Edited now, trying a new framing) Base case: $$H(x,0) = \...
-1
votes
0answers
27 views

How do I obtain the running time for $T(n)=n^2 \sqrt{n}$?

I tried as, $$T(n)=n^2 \sqrt{n} =n^{\frac{5}{2}} $$ On expanding, $$ T(n)=n^{\frac{5}{2}}+n^{(\frac{5}{2})^2}+n^{(\frac{5}{2})^3}+\cdots +n^{(\frac{5}{2})^k} $$ Thus, for $T(1)$ $$n^{(\frac{5}{2})^k}=...
1
vote
1answer
410 views

Help Solve Recurrence Relation T(n) = 3T(n/2) + O(n)

Given recurrence $$T(n) = 3T(n/2) + O(n)$$ $$let\:cn >= O(n)$$ for some constant c I can bound $$T(n)$$ in terms of $$T(n/2)$$ so I have $$T(n) <= 3T(n/2)+cn, \ \ \ \ \ k = 1 \ call$$ So I ...
-1
votes
1answer
29 views

Number of solutions of the two equations

Find the number of integral solutions of the equation: $a+b+c=m$ with $0\gt a\gt b\gt c$ And the generalized version: $a_1 + a_2 + \cdots + a_k = m$ with $ 0\gt a_1\gt a_2\gt \cdots \gt a_k$
1
vote
0answers
15 views

CLRS substitution method “subtracting constant” technique

I'm reading CLRS, and in Chapter 4 it states that if you guess the asymptotic complexity of a recurrence correctly but cannot quite get the mathematical induction work out, a common method to employ ...
1
vote
0answers
32 views

Proving that this recursively defined sequence converges.

The sequence is defined as such, with $a_1=1$, $$ a_{n+1} = \begin{cases} a_n + 1/n, & \mbox{if } a_n^2 \leq 2 \\ a_n - 1/n, & \mbox{if } a_n^2 > 2 \\ \end{cases}. $$ In the book, P.M. ...
0
votes
0answers
29 views

Big O for $T(n) = T(n/2) + 2T(n/4) + O(n)$?

How can I solve the recurrent relation $T(n) = T(n/2) + 2T(n/4) + O(n)$? I don't want to make $2T(n/4) = T(n/2)$. Some searching tells me I should try the Master Theorem. Is there a more intuitive ...
1
vote
1answer
23 views

How do I convert the following relation into a recurrence relation?

I am trying to analyse the time complexity of the fast exponentiation method, which is given as $$x^n= \begin{cases} x^\frac{n}{2}.x^\frac{n}{2} &\text{if n is even}\newline x.x^{n-1} &...
4
votes
1answer
34 views

When is a recurrence the sum of the powers of the roots of a polynomial?

Newton's formula allows one to calculate the sum $S_n(P)$ of the $n$th powers of the roots of a given monic polynomial $P$ without finding the roots explicitly. (This works even when the roots ...
1
vote
2answers
78 views

Help solving this recurrence relation

I wanted to resolve the determinant of the next (nxn) matrix via recurrence relations: $$ \begin{vmatrix} a & 1 & 0 & 0 & 0 & 0 &.... 0 & 0 & 0 & 0 & 0\\ 1 &...
-1
votes
0answers
11 views

Complex and real conditions on steady state stability analysis

I am currently working on a model and I'm trying to find conditions on stability for a point n*. The model is a non-linear difference equation and after calculating and simplifying |f'(n*)|<1 I am ...
0
votes
1answer
19 views

recurrence relation - How to determine pattern for an even or odd or different type of factorial

Hi I am having trouble on how to solve for the odd terms of recurrence relation in terms of exponential and factorials. How are you able to see a pattern to simplify a non standard factorial. This ...
2
votes
1answer
55 views

Linear four-parameter recurrence from Concrete Mathematics

In the book Concrete Mathematics, there's an exercise (1.16) where you're asked to solve a general four-parameter recurrence using the Repertoire Method. The recurrence is defined as follows: \begin{...
1
vote
1answer
30 views

Coverings of a rectangle

How many coverings of the rectangle with height $1$ and length $n$ exist, if we use only tiles with height $1$ of the following 6 types: The solution should be in a closed form (formula).
2
votes
1answer
107 views

Tough Recurrence Relation

I'm trying to find a recurrence equation solution to $$f(n)=a(n)f(n-1)+f(n-2)$$ with the initial conditions that $f(-1)=0, f(-2)=1$ and $$a(n)=\frac{c}{2}(1+(-1)^n)-\frac{d}{n+1}(1-(-1)^n)$$ with some ...
2
votes
1answer
32 views

If $2a_{n+2} \le a_{n+1}+a_n$, then $\lim \sup a_n \le \frac23 a_2 + \frac13 a_1$

This is a reformulation of a deleted question: If $a_1 > 0$ and $a_2 > 0$ and $2a_{n+2} \le a_{n+1}+a_n$, show that $\lim \sup a_n \le \frac23 a_2 + \frac13 a_1$. My proof involves showing ...
0
votes
2answers
64 views

Solve recurrence relation $a(n) = -a(n - 2) + \cos({n} \cdot {\frac{\pi}{2}})$

Given recurrence equation $$a(n) = -a(n - 2) + \cos({n} \cdot {\frac{\pi}{2}})$$ find the closed form solution. Here is my attempt. First solve the homogeneous equation: $$a^{(0)}(n) = -a^{(0)}(n - ...
1
vote
2answers
37 views

How to solve this recurrence $T(n) = \log{n}*T(n/\log{n})+\sqrt{n}$

I tried substitution for $2^n$ or $2^{\log{n}}$ or even $2^{2^n}$ and it didn't work. Thanks! :)
2
votes
3answers
35 views

Trying to solve non-homogeneous linear recurrence relation with difficult non-homogeneous part

I have the following recurrence relation that I'm trying to solve: $$f(n)=2f(n-1)-f(n-2)-2$$ The homogeneous part is easy: The characteristic polynomial $r^2-2r+r=0$ has root $r=1$ with ...
1
vote
0answers
28 views

Finding functions that give nice solutions to a recurrence relation.

In a recent problem I was working through, I came across the following recurrence relation: $$ \text{K}_1(x,\ t;\ g) = 1,\quad x, t\in\Bbb{R}\quad g\in\text{C}^1 \\ \text{K}_{n+1}(x,\ t;\ g) = g'(t)\...
0
votes
1answer
50 views

Thought-provoking functional computation problem

I have been assigned a very thought-provoking functional computation problem (to be completed $without$ a calculator) which has left me essentially stumped—that is, I really can't come up with an ...
0
votes
0answers
19 views

What is the method for solving this recurrence relation?

I have an equation for generating square-triangle numbers using a recurrence relation: $$f(n)^2+f(n)(2-34f(n-1))+(f(n-1)^2-70f(n-1)+1) = 0$$ But I wish to solve the equation to produce a closed form ...
0
votes
0answers
32 views

How can I solve this recurrence relation for generating triangle-squares?

$$N_k = 17N_{k-1} + 6(8N^2_{k-1} + N_{k-1})^{1/2} + 1$$ $$k\geqslant 1$$ I'm trying to convert a recurrence relationship for producing triangle square-numbers into a closed-form expression in terms of ...
1
vote
1answer
453 views

Solving recurrence relation: $ f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$

$f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3$ I have attempted to solve it by letting $n = 2^k$ $f(2^k) = 3f(2^{k-1}) - 2f(2^{k-2})$ Then set $S(k) = f(2^k)$ $S(k) = 3*S(k-...
0
votes
1answer
41 views

How to solve this recursion?

If $r>0$ holds and recursion is given by $T(r)=\alpha T(r^{1/\alpha})+\alpha r^{1/\alpha}$ where $\alpha\geq 2$ is fixed and assume $T(r)=O(1)$ for $r\leq1$. What is $T(r)$?
3
votes
2answers
78 views

What is the intuitive idea behind looking for a solution of the form an=r^n for a linear homogeneous recurrence relation?

In my textbook, under solving linear homogeneous recurrence relations, it says that the basic approach for solving them is to look for a solution of the form an = rn, which yields the characteristic ...
2
votes
2answers
453 views

Recursive random draw

Let $R(n)$ be a random draw of integers between $0$ and $n − 1$ (inclusive). I repeatedly apply $R$, starting at $10^{100}$. What’s the expected number of repeated applications until I get zero?
3
votes
1answer
604 views

Recurrence Relation, Discrete Math problem(Homework)

There is a disk, separated into n sections, as indicated in the graph. For each section, you can paint it with one color out of four: Red, Yellow, Blue, Green. The rule is adjacent sections can't have ...
1
vote
4answers
84 views

Closed form of recurrence relation $F(n) = 2 + F(n-1) + F(n-2)$

I was figuring out an answer to the question, How many Boolean arrays of length $n$ could be formed if there are to be no two falses in a row? I could see that it boils down to a Fibonacci ...
0
votes
2answers
26 views

Finding the generating function of a recurrence relation in dependence of a variable

Given this inhomogeneous linear recurrence relation of 2nd order : $F_n = F_{n-2} + a$ for $n \geq 2$ with $F_1 = 1$ and $F_0 = 0$ How do I find the generating function of this recurrence ...
0
votes
0answers
9 views

2D recurrence relation

Lately I encountered following DE: $$ x O^\alpha f\left(x\right) = f\left(x\right)-1 $$, where $$ O f\left(x\right) = x f'\left(x\right) + f\left(x\right) $$ It can be solved using a solution to the ...
34
votes
2answers
744 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
0
votes
1answer
67 views

$a_{n+1} = (a_n+1)a+(a+1)a_n+2\sqrt{a(a+1)a_n(a_n+1)} \quad (n = 1,2,\ldots).$

Let $a$ be a positive integer and $\{a_n\}$ be defined by $a_0 = 0$ and $$a_{n+1} = (a_n+1)a+(a+1)a_n+2\sqrt{a(a+1)a_n(a_n+1)} \quad (n = 1,2,\ldots).$$ Show that for each positive integer $n$, $a_n$ ...
1
vote
1answer
31 views

Josephus problem: the renumbering method from Concrete Mathematics

In Concrete Mathematics, Chapter 3, Section 3, an interesting method to solve the Josephus problem is discussed. The paragraphs below depict the method, which are extracted from the book: (Initially, ...
1
vote
4answers
83 views

Finding a closed form for $\sum^{n}_{k=1} \frac{k}{(k+1)!} $

I'm finding a closed form to $\sum^{n}_{k=1} \frac{k}{(k+1)!} (n \leq 1) $ (in a environment of induction and recurrence) I've been trying to solve it without success, can anybody help me (?) The ...
1
vote
0answers
61 views

Solving a non-standard linear recurrence [closed]

Can you find an expression for the sequence $(a_n)$ satisfying the following recurrence $$a_n = a_{n-1} + a_{n-2} + \sum_{i=3}^{n} 2\binom{n}{i}a_{n-i}$$ for $n \geq 3$ where $a_0 = 0, a_1 = 1, a_2 ...
2
votes
0answers
25 views

Is it possible to find the nth term of this recursive sequence?

I have the following sequence: $$x_n= y - sgn(x_{n-1}) \cdot |b\cdot x_{n-1} - c|^{0.5}$$ $$x_1=0$$ Is there a way to find $x_n$ without knowing $x_{n-1}$?
1
vote
1answer
32 views

Using determinants to find a recursive sequence

I am trying to compute a three diagonal determinant in order to find the recursive relation. Let $\Delta_{n}$=$\begin{vmatrix} 11 & 3 & 0 & 0 & \dots & 0\\ 13 & 11 & 3 &...
0
votes
0answers
37 views

Proving that one sequence is greater than another using a recurrence inequality

I'm trying to understand the proof of proposition 2 from All reductive p-adic groups are tame, Bernshtein. In the article there are given two sequences of functions $\{{f_l}\}_{l=0}^\infty$, $\{{\...
1
vote
0answers
44 views

Solving recurrence relation $a_n=1 + \sum\limits_{i=1}^{n-1}ia_{n-i}$ with $a_1=1$

Consider the recurrence relation $$a_n=1 + \sum_{i=1}^{n-1}ia_{n-i}$$ with initial term $a_1=1$. What is $a_n$? I tried to guess some closed formula from the first 6 terms, which are $1$, $2$, $5$, $...
19
votes
4answers
5k views

Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...
0
votes
1answer
23 views

Solving Recurrence Relations with generating functions when the variable is in the function.

I'm studying for a midterm and couldn't figure out these three recurrences that I came across: $i_{n+1}=2ni_n+2i_n+2$ with initial condition $i_0=1$ $j_{n+1}=3j_n+1$ with initial condition $j_1=1$ $...
0
votes
2answers
28 views

Recurrence: Theta of t(n) = 4t(n-1) -15

First let me start off by saying that I am using the substitution method to solve this equation.Although any other methods will be welcomed, this is just the particular method I feel comfortable with. ...
0
votes
3answers
69 views

Find recurrence relation with general solution $a_n=A+Bn+C2^n+\frac{1}{3}n2^{n-1}$

General solution is: $a_n=A+Bn+C*2^n+\frac{n}{3}*2^{n-1}$ Can you give me some tips on solving this? Any help would be appreciated.
0
votes
1answer
21 views

Express $T(n) $as a recurrence relation and derive and expression for $T(n)$ in terms of $n$.

Question: $T(n)$solves the problem by breaking it up into 4 sub problems of the same kind, each of size $n/4$. The solution to the original problem is obtained by combining the solutions of the $4$ ...