# Tagged Questions

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

112 views

26 views

### Cardinality of a set with a recurrence relation.

Let $A = \left\{ f\in \mathbb{N}\rightarrow \mathbb{C} \mid \forall n\in \mathbb{N}. f(n+3) + 3f(n+1) = f(n+2)+f(n) \right\}$ What is $\left|A\right|$? Well, I tried to treat $f$ as a recurrence ...
71 views

### Concerning a specific family of recursive sequences

There is a family of recursive sequences that I came up with: $$a_n=\text{sum of factors less than a_{n-1} of } a_{n-1}, a_0\in\mathbb{N}$$ First question: Has it been studied before? Here are ...
82 views

70 views

### Understanding a recurrence relation question.

A computer system considers a bit string a valid codeword if and only if it does not contain $3$ consecutive zeroes. Thus $010010$ is a valid codeword of length $6$ while $011000$ is not. Let $a_n$ be ...
89 views

### Recursive Function - $f(n)=f(an)+f(bn)+n$

I've got this recursive function $f(n)=f(an)+f(bn)+n$, and I need to find $θ$ on $f(n)$, as $a+b>1$. Using a recursive tree, I managed to bound it by $n\log(n)$ from the bottom and by $n^2$ from ...
38 views

### Given initial conditions and a recurrence relation, what is closed form in terms of n?

We are given that $a_0$ = 1000, and $a_1$ = 3000, and that $\forall n \geq 2$, $a_n = \frac{a_{n-1} + a_{n-2}}{2}$. What is the value when $n$? I've determined that, in the long run, it converges to ~...
34 views

### Why does $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$ imply $T(n)=\mathcal{O} (n\log(n))$

I am learning about sort algorithms and their complexities. For merge sort, I'm confronted with $T(n) \leq 2 T(\lceil \frac{n}{2} \rceil)+\mathcal{O}(n)$. The author makes the claim with no ...
346 views

### Number of n-digit ternary sequences with an even number of 0's and 1's

Can someone help me derive a recurrence relation to find the number of n-digit ternary sequences with an even number of 0's and 1's? I know that you need to break it down into cases where the ...
70 views

### How can I get the following recursive relation that explained?

if $b(n)$ is the number of words created by the alphabet ${a,b,c}$ with $n$ length that each word has at least one $a$ character and after each $a$ there is no $c$ character write a recursive relation ...
33 views

### How does one find annihilators for recurrence relations?

I've recently taken an interest in the Method of Annihilators for solving recurrence relations. However, I taught myself using nearly solely this Power Point presentation. Thus, my knowledge is ...
29 views

2k views

105 views

### Recurrence $a_{n+1} = xa_n$ using generating function

I read the generating functionology, where author handles $$b_k(x) = {x \over 1-kx} b_{k-1}(x) = {x ^k \over (1-x)(1-2)(1-3x) \cdots (1-kx)}$$ since $b_0(x) = 1.$ I see that if denominator $(1-kx)$ ...
141 views

### Recurrence relation: $x_{n+1} = \frac 12 x_n + \frac 1 {x_n},$ [duplicate]

$$x_{n+1} = \frac 12 x_n + \frac 1 {x_n}, x_0 \neq 0$$ $$a = \frac a2 + \frac 1a \Rightarrow a = \frac {a^2 + 2} {2a} \Rightarrow 2a^2 = a^2 + 2 \Rightarrow a^2 = 2 \Rightarrow a = \pm \sqrt 2$$ If ...
89 views

### solution of recurrence relation $x_{n+1} = \frac {1}{x_n + 1}$

$$x_{n+1} = \frac {1}{x_n + 1}; x_1 > 0$$ How to transform it into the form $x_n =$? I need the solution in order to check if it converges at any $x_1 > 0$.
598 views

42 views

### Details about a Recurrence Relation problem.

I am trying to understand Recurrence Relations through the Towers of Hanoi example, and I am having trouble understanding the last step: If $H_n$ is the number of moves it takes for n rings to be ...
168 views

### How many times can a student skip class in a 14 weeks semester?

In a 14 weeks semester there are 5 school days each week. Johnny chooses each day if he goes to the University or skips the day. In how many ways can Johnny choose his attendance during the semester ...
Given the following recurrence equation: $T(n)=T\left(\dfrac{n-1}{2}\right)+2$ , $T(1)=0$ How would you set this equation up in order to allow you to solve it using telescoping? Thanks in advance.
### Convergence of $x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$
$x_n=\sqrt{2(x_{n-1}-\log(1+x_{n-1}))}$ with $x_0=a\ge0$ I calculated some values for $x_n$ with $a=0,1,2$ and recognized its monotonically decreasing (It converges to $0$). Now the standard approach ...