# Tagged Questions

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

15 views

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 ...
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 ...
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. ...
56 views

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 ...
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$
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 ...
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. ...
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 ...
23 views

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 ...
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 ...
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{...
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).
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 ...
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 ...
64 views

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 ...
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 ...
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 ...
453 views

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}$?
32 views

44 views

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. ...
### 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.
### 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$ ...