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

learn more… | top users | synonyms

2
votes
3answers
59 views

Proof by induction of a recursive sequence

I am studying CIE A levels Further Maths and I am stuck at a question from June 2002: Q The sequence of positive numbers $u_1,u_2,u_3,...$ is such that $u_1<4$ and ...
2
votes
1answer
55 views

Find the generating function for a series , given a recurrence relation

I am solving a problem on an Online Judge. The problems solution boils down to find the solutions to the following recurrence relation: ...
2
votes
1answer
73 views

Recurrence relation converting to explicit formula

Let $a_n = -2a_{n-1 }+ 15a_{n-2 }$ with initial conditions $a_1 = 10 $ and $a_2 = 70$. a)Write the first 5 terms of the recurrence relation. b)Solve this recurrence relation. c)Using the explicit ...
2
votes
5answers
91 views

How to find first five terms of sequence?

I'm new to recursion so please bear with me. I have to find the first five terms of a sequence with initial conditions $u_1 = 1$ and $u_2 = 5$, and, for $n \geq 3$, $$u_n = 5u_{n−1} − 6u_{n−2}.$$ I ...
2
votes
1answer
35 views

Recurrence relation and big-O-notation

Consider the following recurrence relation: $$T(n)=c\cdot + 2\cdot T(n/2)$$ This is the recurrence relation for the Merge-Sort algorithm. How can one deduce from this equation the time complexity of ...
2
votes
1answer
55 views

Generating Function for Recurrence Relation in 2 Variable

I have a recurrence relation with 2 variables similar to $$ F(n,m) = n\cdot F(n-1,m) + (n-m)\cdot F(n-1,m-1) $$ I want to know the steps required to get the generating Function for such recurences. I ...
2
votes
1answer
46 views

Solving the recurrence relation $T(n) = (n+1)/n*T(n-1) + c(2n-1)/n, T(1) = 0$

I tried a lot of different methods. Not able to make out the series. Could anyone help me i this regard? $ T(n) = \frac{(n+1)}{n}T(n-1) + c\frac{(2n-1)}{n} , T(1) = 0 $
2
votes
2answers
62 views

Got stuck in proving monotonic increasing of a recurrence sequence

I'm stuck with the prove of the following recurrence sequence which was part of and old exam. $a_1:=\frac{1}{2}, a_{n+1}:=a_n(2-a_n)$ for $n \in \mathbb{N}$ I have to show that $0 <a_n < 1$ ...
2
votes
2answers
55 views

Question with recurrence - Check my answer and suggest better ideas

Every morning when he gets up, Oria leaves the house for a walk. he walks exactly $n$ steps. He can walk only forward, right, or left, and he will never turn left immediately after he turned right, ...
2
votes
5answers
106 views

Finding a recurrence relation in combinatorics

First, my English is not that good so please don't laugh. I need to find a recurrence relation for : The number of words with the length of n that could be composed from the letters A,B,C,D, so the ...
2
votes
1answer
50 views

Recursive Definition for Logarithm

Is it possible to express $\log(n)$ in terms of itself, using only elementary functions, e.g., similar to (the incorrect made-up equation): \begin{equation*} \log(n) = e^n * \log(n - 1) + \sin(n) * ...
2
votes
1answer
105 views

The annihilator of $n(2^n)\sin({n\pi \over 2})$

I have to solve this problem: $y(n+2)-y(n)=n(2^n)\sin({n\pi \over 2})$ And I know the annihilator of $n(2^n) = (E-2)^2$, but I don't know how I should find the other part of the annihilator. ...
2
votes
1answer
113 views

Closed form solution to a recurrence relation (from a probability problem)

Is there a closed form solution to the following recurrence relation? $$P(i,j) = \frac{i^{5}}{5i(5i-1)(5i-2)(5i-3)(5i-4)}\sum\limits_{k=0}^{j-5}(1-P(i-1,k))$$ where $P(i,j)=0$ for $j<5$. The ...
2
votes
1answer
73 views

Recurrence relations - simple questions, please verify my answers.

I'm posting this question because this is new material for me and I am unsure of my answers and have no one to consult with. I solved the first three and would appreciate feedback. I need help solving ...
2
votes
1answer
94 views

How find this function $f(2^m)=?$

show that:there exists unique function $f:N^{+}\to N^{+}$,such $$f(1)=f(2)=1$$ and $$f(n)=f(f(n-1))+f(n-f(n-1))),n=3,4,\cdots$$ and Find $f(2^m),m>2,m\in N$ My try: let $n=3$ ,then we have ...
2
votes
1answer
245 views

Recurrence relations question

A vending machine dispensing books of stamps accepts only one-dollar coins, $1 bills, and $5 bills. a) Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, ...
2
votes
1answer
53 views

How to solve this specific recurrence relation

I'm trying to solve the following recurrence relation for $\alpha_j$, for which Mathematica is not helpful. $$ \lambda\alpha_j + (j+1)\alpha_{j+1} = \sum_{\mu = ...
2
votes
1answer
353 views

Recurrence relation and ternary sequences

I had a question that I need some help on: Find and solve a recurrence relation for the number of n-digit ternary sequences with no consecutive digits being equal As I worked this out, I ...
2
votes
2answers
411 views

Nonhomogeneous Recurrence Relations

Solve the nonhomogeneous recurrence relation $$h_{n}=3h_{n-1}-2$$ $$n\geq 1$$ $$h_{0}=1$$ I have been told to approach this type of problem using two steps. First, solve the corresponding ...
2
votes
1answer
34 views

Simple recurrence relation - 1D

I know this is a very simple recurrence relation, but how would you go on solving it? $$x(n+1)=\frac{x(n)}{1+x(n)}$$
2
votes
1answer
103 views

Basis for recurrence relation solutions

So, I have a question: Imagine a recurrence relation $U(n+2) = 2U(n+1) + U(n)$. How do I determine the dimension (and the vectors that constitute the basis) of a vector space which contains all ...
2
votes
1answer
78 views

Looking for bounds of a recursively defined sequence

I'm looking for the tightest upper and lower bounds on the sequence defined recursively by $a_{0}=1$ and $a_{n}={\displaystyle \sum_{k=0}^{n-1}\frac{4}{n^{2}}a_{k}+c\cdot n}$ for $c>0$. It is ...
2
votes
1answer
57 views

How to prove and derive coefficients that an exponential whose base decreases exponentially is a parabola

Suppose I have a function defined by this recurrence-relation: $$R(0) = r$$ $$R(n) = R(n-1) * (1+G)d^{n-1}$$ Here r is a base value, G is a base growth rate (G>0) and d is a decay in the growth rate ...
2
votes
3answers
552 views

Solving recurrence equation using exponential generating functions

The recurrence is $ a_n = (n-1) a_{n-1} + (n-2)a_{n-2} $ I tried using exponential generating functions and have problems with it (the second term mostly) Further can this be solved without ...
2
votes
2answers
69 views

Finding the coefficient in the closed form of the generating function

I try to solve the recursion $a_n=5a_{n-1}+5^n$ with $a_0=1$ with generating function, but I could not find the coefficient of $x^n$ in the closed form \begin{eqnarray*} ...
2
votes
2answers
80 views

Recurrence Relations for $c_1$ and $c_2$

For the following recurrence relation: $a_n = 3a_{n-1}+4a_{n-2}$, where $a_0=3$ and $a_1=2$ I solved it using quadratic equation by $x^2+3x-4$. So I got to $a_n = 4^nc_1 + c_2(-1)^n$. Now to find ...
2
votes
2answers
77 views

Finding the expression for $q_n$

Let $q_n$ be the number of $n$-letter words consisting of letters a, b, c and d, and which contain an odd number of letters $b$. Prove that $$q_{n+1} = 2q_n + 4^n\qquad\forall n \geq 1 $$ and, ...
2
votes
1answer
52 views

Recurrence equation question

My question (which has been edited) relates to the following recurrence relation: $$a_{j+2}=\frac{2 a_{j}}{j}$$ The book which I am reading says that the (approximate) solution is given by: ...
2
votes
1answer
48 views

Finding functional equation for generating function

I'm given $$ a_n = \sum_{i=2}^{n-2} a_ia_{n-i} \quad (n\geq 3), a_0 = a_1=a_2 = 1 $$ and I need to find the functional equation for the generating function satisfying the above equality. I obtained ...
2
votes
1answer
138 views

Pascal Triangle Related Problem: Fibonacci Sequence on sides

I have this triangle: $$\begin{array}{} &&&&&&&1\\ &&&&&&1&&1\\ &&&&&2&&2&&2\\ ...
2
votes
1answer
917 views

Showing that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$

How can we prove that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$? What is the resulting equation I get after the substitution? $$ T(n) = 2c \cdot \frac n2 \cdot \log \frac n2 + 17 + n $$ ...
2
votes
1answer
75 views

Constant term of recursively defined polynomials related to the Lambert W function

The Lambert $W$ function has the property that $$ W'(x) = \frac{W(x)}{x[1+W(x)]}, $$ and using this one can show that its Taylor expansion about $x=a$ has the form $$ W(x) = W(a) + ...
2
votes
1answer
516 views

Concrete Mathematics - The Josephus Problem

I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem. Recurrent relation: $J(1) = 1$ $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + ...
2
votes
4answers
420 views

Solving Recurrence T(n) = T(n − 3) + 1/2;

I have to solve the following recurrence. $$\begin{gather} T(n) = T(n − 3) + 1/2\\ T(0) = T(1) = T(2) = 1. \end{gather}$$ I tried solving it using the forward iteration. $$\begin{align} T(3) ...
2
votes
2answers
114 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
156 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
522 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
234 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
134 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
246 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
163 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
81 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
967 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
2k 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
94 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 ...