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

learn more… | top users | synonyms

2
votes
2answers
113 views

When is a linear recurrence relation solvable?

I was reading this definition of a linear recurrence, and was wondering what characteristics are required of a linear recurrence for it to be solvable? Meaning, can I find a closed form? The subject ...
2
votes
2answers
68 views

Integral expansion help!

So I'm very close to finishing a proof of the exponential function in terms of differential equations. For this next step, I have to show the following. For $n \ge 0$ define $E_n (t)$ recursively ...
2
votes
1answer
153 views

Basic recurrence problem, not sure if solution is correct (solution included)

I have the following exercise: We know that the solution of $T(n) = 2T(n/2) + n$ is $\mathcal{O}(n \log_2 n)$. Show that the solution of this recurrence is also $\mathcal{\Omega}(n \log_2 n)$. ...
2
votes
2answers
516 views

Solving recurrences $T(n) = 4 T(2n/3) + (n^3 )\cdot \log(n)$

I have a recurrence: $T(n) = 4 \cdot T\left(\frac{2n}{3}\right) + (n^3 )\cdot \log(n)$ how can this case be solved from master theorem as this is not in the general form of $T(n) = aT(⌈n/b⌉) + ...
2
votes
1answer
224 views

What's the generalized approach for solving non homogenous recurrence relations?

I am trying to understand how do you solve non homogenous recurrence relations. So , for example, consider the following equation, $$(A-2)^2(A-1)g = 3(n^2)(2^n) + (2^n)$$ So , $A$ being the ...
2
votes
2answers
52 views

solve $n^{{1/2}^k} = 1$ for $k$

I am trying to find the time complexity for the recurrence $T(n) = 2T(n^{1/2}) + \log n$. I am pretty close to the solution, however, I have run into a roadblock. I need to solve $n^{{1/2}^k} = 1$ for ...
2
votes
3answers
131 views

Recurrence relation, find general term

How do you find the general term of this recurrence relation? $A(n)=c n+A(\lfloor n/2 \rfloor)$ for $n>2$, $ A(n) = 1 $ for $n=2$, where $c$-constant
2
votes
1answer
63 views

Flawed twofold induction on an inequation (but where?)

The following induction is flawed because the result admits a counter-example, but I can't find where is the flaw. Please advise. [Edit: As pointed out in the answer, the error was in the base case. ...
2
votes
3answers
56 views

Getting the recurrence formula with a condition

Get the recurrence formula of $$U_n=2(-3)^n-5n(-3)^n$$ For $$n \geq 1$$ What am I supposed to do with this condition $n\geq 1$?
2
votes
1answer
75 views

Recurrence sequence over the complex field

Consider the following recurrence relation $$z_{n} = c^2 + 2cz_{n-1}^2 + z_{n-1}^4 - (c+c^2)z_{n-1} - 2cz_{n-1}^3 - z_{n-1}^5$$ where $z_{n}, c \in \mathbb{C}$. I google a while but the formula for ...
2
votes
1answer
243 views

Number of permutations with a certain number of fixpoints

Given a set of $n$ mutually distinct elements, how many permutations are there such that exactly $k$ of the permuted elements stay at the same place? Example Let's take the set $\{A,B,C,D\}$. The ...
2
votes
1answer
162 views

Solve the recurrence: $Q_0=\alpha$; $Q_1=\beta$; $Q_n=(1+Q_{n-1})/Q_{n-2}$, for $n>1$.

This one is from "Concrete Mathematics": Solve the recurrence: $Q_0=\alpha$; $Q_1=\beta$; $Q_n=(1+Q_{n-1})/Q_{n-2}$, for $n>1$. Assume that $Q_n \neq 0$ for all $n \geq 0$. I ...
2
votes
1answer
79 views

Recurrence of Log function

I have the equation $T(n) = 4T(n/2) + n + log(n)$ for $n\ge2$. I am considering the case where $n=2^k$ I have come to the conclusion that $T(n)$ follows the following formula: $$\begin{align*}T(n) ...
2
votes
2answers
958 views

Recurrence $T(n)=2T([n/2]+17)+n$ and induction.

Show that the solution to $$T(n) = 2T\left(\biggl\lfloor \frac n 2 \biggr\rfloor+17\right)+n$$ is $\Theta(n \log n)$? So the induction hypothesis is $$ T \left( \frac n 2 \right) = c\cdot \frac n2 ...
2
votes
1answer
1k views

Proving a recurrence relation with induction

I've been having trouble with an assignment I received with the course I am following. The assignment in question: Use induction to prove that when $n \geq 2$ is an exact power of $2$, the solution ...
2
votes
1answer
90 views

Showing two recurrences to be identical

I am trying to prove Cayley's formula for number of labelled trees on n vertices using multinomial coefficients. The multinomial coefficient satisfies the recurrence: $\tbinom{n}{r_1,\cdots ...
2
votes
3answers
132 views

Solve recurrence equations-homework extras

Extras from my homework. The first one should be easier, but still hard enough. 1) $a_{n+3}-(3/2)a_{n+2}-a_{n+1}-(1/4)a_n=0$ 2) $a_{n+3}-3a_{n+2}-3a_{n+1}+a_n=n^2+2^n$
2
votes
2answers
337 views

Solving recurrences of the form $T(n) = aT(n/a) + \Theta(n \log_2 a)$

The time complexity for the merge sort algorithm is $T(n) = 2T(n/2)+\Theta(n)$, and the solution to this recurrence is $\Theta(n\lg n)$. However; assume you are not dividing the array in half for ...
2
votes
2answers
368 views

Second Order Homogeneous Recurrence Relation Question

I am revising for an exam in a few weeks and I have the following recurrence relation: f(1) = 1 f(2) = 2 f(n) = 5f(n/2) - 4f(n/4), n > 2 My lecture notes are ...
2
votes
1answer
70 views

Quadradic recurrence relation

There is an method to solve recurrences of the form $a_{n+1} = (a_n + c)^2$? I am particularly interested when $c = 1$. I tried to use generating functions but I got stuck with. Let $G(x) = \sum_{k ...
2
votes
1answer
44 views

Recursive formula for creating a specific string

I have 5 characters ${a,b,c,1,2}$. $a_n$ is the number of strings I can create for $n$ length. I can't have the following sequences in a string: $a1$, $b2$ and any sequence of numbers $(12, 21)$. For ...
2
votes
1answer
54 views

Number of ways to derive the number 14 using a recursive definition of EVEN numbers?

I have the following recursive definition for the construction of EVEN Numbers- [RULE 1]: 2 is an EVEN number. [RULE 2]: If x is an EVEN number and y is an EVEN number, then x+y is also an EVEN ...
2
votes
0answers
32 views

Linear Independence of Powers of “roots vector” [duplicate]

Let us be working over the field of complex numbers. Suppose $f(x)= a_n x^n + \cdots +a_1 x + a_0$ is a degree $n$ polynomial with $n$ distinct roots $z_1,\ldots,z_n$. Is the following matrix always ...
2
votes
2answers
36 views

A mixture of AP and GP

A battery loses $10$ mAh of after every hour when in use. The same battery loses $1\%$ of its current amount of charge every hour when not in use. Suppose that the battery is fully charged with ...
2
votes
1answer
44 views

Techniques for solving recurrence relations using generating functions

How does one extract coefficients from generating functions that involve exponents. Things like $A(z) = 1+A(z^2)$ or $A(z)= 1+A(z^2)+A(\sqrt z)$?
2
votes
0answers
26 views

Verify that this recurrence relation is in O(log n)

For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$ My attempt at a solution (mostly just wanting to verify its correct). Lower Bound: $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ ...
2
votes
1answer
48 views

Expected Time for n Independent Prisoners to Escape

Suppose there are $n$ prisoners, and each day every prisoner independently has a probability $p$ of escaping. What is the expected length of time before all prisoners have escaped? Someone asked ...
2
votes
1answer
47 views

Arithmetic function

An arithmetic function is defined as follows:$f(1)=1$, $f(2k)=k$ and $f(2k+1)=f(k)+f(k+1)$. When (for which $k$) is $f(k)$ even? While it is obvious that $f(4n-1)=f(4n)=2n$, therefore $f(k)$ is even ...
2
votes
2answers
88 views

A sequence in which $x_n$ depends on all of $x_0, … x_{n-1}$

A particular combinatorial sequence I was looking at turned out to obey the following pair of recurrence relations: $$N_{2n+1}=\sum^n_{k=0}N_{2k}$$ ...
2
votes
1answer
75 views

Solve the recurrence relation:$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\sqrt{n}$ [closed]

I have doubt in solving the following questions: $T(n)=2T(\sqrt{n})+n$ $T(n)=\sqrt{n}T(\sqrt{n})+c$ $T(n)=\sqrt{n}T(\sqrt{n})+\sqrt{n}$ T(2)=1 for all the problems Atleast give the final answer.
2
votes
2answers
76 views

Process of solving recurrence relations

I am having trouble understanding how to solve a recurrence relation. If you can please help walk me through this one: $T(n) = T(\dfrac{n}{2}) + 5$ Initial conditions $T(0) = 0$ and $T(1) = 1$ My ...
2
votes
2answers
107 views

How to find fixed point

I have recurrence equations of \begin{align*} x_{n+1} &:= 0.5\cdot (x_{n}^2+2\cdot y_{n}-2\cdot x_{n}\cdot y_{n}-2\cdot y_{n}^2) \\ y_{n+1} &:= -0.8\cdot (x_{n}^2+2\cdot y_{n}-2\cdot ...
2
votes
0answers
92 views

How to solve a ceiling expression or recurrence equation?

I am trying to express the following in term of n, $$\underbrace{\hbox{$ \left \lceil \frac{3}{2}.\left \lceil { \frac{3}{2}.\left \lceil { \ldots \left \lceil \frac{3}{2}.\left \lceil { ...
2
votes
1answer
31 views

Four or More Heads in a Coin Toss

How would one write a recursion for the number of ways to get 4 or more heads in a row in 10 tosses of a coin? Would it suffice to use the recursion H(n)=H(n-1)+H(n-2)+H(n-3)+H(n-4) for the number of ...
2
votes
0answers
134 views

Special map $f(x_n)=x_{{n+1} [\mod 4]}$

As mentioned in the headline I am considering the map $f(x_n)=x_{{n+1} [\mod 4]}$. It looks a little bit similar to the dyadic (bernoulli) map but instead of $\mod 1$ we have $\mod 4$ which means that ...
2
votes
1answer
48 views

What is the relationship between a non homogenous second order difference equation (constant coefficients) and its derivative?

Here's an excerpt of a lecture note I am reading (I've highlighted the beginning of the part that I don't understand): I don't understand how derivative comes into the picture. Here's some context ...
2
votes
1answer
50 views

Justifying onto function properties

For $m,n\ge0$ let $O(m,n)$ be the number of onto functions a) Explain why $O(m,n)=0$ when $m\lt n$ I said: since O is an onto function it implies that for all elements of n there is atleast one m ...
2
votes
0answers
44 views

(limit of) a linear second order recurrence relation with variable coefficients

I have the following recurrence relation: $(n + 1) a_{n + 2} = (w (n + 1) - c) a_{n + 1} - z (n + 1)*a_{n}$ that I would like to either solve, or to get the $n$ goes to Infinity limit of the ratio ...
2
votes
0answers
163 views

Induction proof of a recurrence relation

I have some trouble with an induction proof for the following problem. There is a vending machine that only takes coins of value 1 and 5 respectively. Let $S_n$ be the number of different ...
2
votes
0answers
29 views

Determinant of Stirling submatrix

Consider the table containing the Stirling numbers of the second kind $S\left( n,k\right) $. From this table construct a square matrix $M$ containing $N$ differents rows from the table ...
2
votes
1answer
88 views

What is the bound of: $T(n) = T(n-2) + (n)log(n)$?

I am given the following recurrence relationship: $\ T(n) = T(n-2) + nlog(n)\\ T(1) = T(0) = constant$, I need to find the order for the recurrence. So, using the iterative methodology, what I ...
2
votes
0answers
83 views

How to solve this recurrence relation (related to discrete Fourier transform)?

I am having trouble with the following recurrence relation: $$c_{n+1} - c_{n-1} = 2\alpha \sin \frac{(2n-1)\pi}{N} c_n, \quad\forall n \in \mathbb{Z},$$ where $N$ is odd and the initial condition is ...
2
votes
2answers
121 views

Solve a recurrence relation with $\sqrt n$ inside.

I have never seen such an equation: $$T(n) = T\left(\frac n2 + \sqrt n\right) + n$$ Is it possible to solve? If yes, how? I mean is there any general method for it or something? thanks.
2
votes
0answers
53 views

Recurrence relation for polygamma reflection polynomials

In the reflection formula for the polygamma function $$ \psi^{(n)}(1-z) + (-1)^{n+1}\psi^{(n)}(z) % = (-1)^{n} \pi \frac{d^{n}}{d z^{n}} \cot (\pi z) $$ the right hand side is a polynomial ...
2
votes
1answer
124 views

Numerical Solution of difference equation

I am trying to solve a nonlinear difference equation of the form: $x_{i+1} = f(x_i, x_{i-1})$ for $i = 0,\ldots,N-1$ with given boundary conditions $x_0 = a$ and $x_N = g(x_{N-1})$ where $f$ and $g$ ...
2
votes
1answer
151 views

How to find a closed form formula for the following recurrence relation?

I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm - $$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with ...
2
votes
1answer
87 views

Questions about $\ln(z)$ recurrence and fixed points.

Define property $A_R$ for an analytic function $f(z)$ as $1)$ $f(z)=0$ has exactly one solution being $z=0$ for $|z|<R$ where $R$ is a radius. And $f(z)$ is analytic within the radius $R$ ...
2
votes
1answer
48 views

recurrence relation dependent inversly on n

Is there any efficient way to solve $F(n)=F(n-1)+1/n$ on $\mathcal{O}(\log n)$ time like we have matrix expo. for fibonacci series ?
2
votes
0answers
90 views

Showing the relationship between Lucas and Fibonacci numbers with a recursive relationship

Given the equation $$L_{n+k}-(-1)^kL_{n-k}=5F_kF_n$$ Where $\{L\}$ is the set of Lucas numbers and $\{F\}$ is a Fibonacci sequence, $n$ and $k$ are both $>0$ and integers, how would one develop ...
2
votes
0answers
69 views

How prove this sequences have limts and find this value?

let $f:R\longrightarrow R$,and $f(x)=x-\dfrac{x^2}{2}$,and $$L_{1}(x)=f(x),L_{2}(x)=f(f(x)),L_{3}(x)=f(L_{2}(x)),\cdots,L_{n}(x)=f(L_{n-1}(x))$$ and let $$a_{n}=L_{n}\left(\dfrac{17}{n}\right)$$ ...