# Tagged Questions

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

17 views

### Prove that the entries in this matrix essentially consists of the Dirichlet inverse of the Euler totient.

The identity matrix satisfies the following recurrence: ...
10 views

### Generating function for recurrence raised to powers

Well, there are many recurrence relations as $\displaystyle a_n^{k_n} = \sum_m {f(a_m^{k_m})}$ So, I was thinking if there is a method(a particular kind of generating functions which deals with ...
46 views

### Bibliography and references about approximations or definitions by recursion

Im curious about the topic of approximate or write some function as a recursion, i.e., the opposite to pass a recursion to a closed form or similar things. Im interested in these kind of topics ...
22 views

### fibonacci recurrence problem. [duplicate]

The Fibonacci numbers Fn are defined by the recurrence Fn=Fn−1+Fn−2, with base cases F0=0 and F1=1. Prove that any non-negative integer can be written as the sum of distinct and non-consecutive ...
52 views

### Recursion Tree method for solving Recurrences

I'm trying to find the tight upper and lower bounds for the following recurrence: T(n) = 2T(n/2) + 6T(n/3) + n^2, if n >= 3 = 1 if n <= 2 Drawing the ...
30 views

### Recursion to explicit formula

I need to try to figure out the explicit formula of the sequence $x_n=\frac{(x_{n-2}+x_{n-1})}{2}$ where $x_1=0, x_2=1$. I calculated the first few terms of the sequence and graphed it, but I'm just ...
54 views

### How to solve the non-homogeneous linear recurrence $a_{n+1} - a_n = 2n+3$, given that $a_0=1$?

The problem: $a_{n+1} - a_n = 2n+3$, given that $a_0=1$ First I solved the associated homogeneous recurrence and got $a_n = A(1)^n = A$, where A is a constant, but I got stuck solving the rest. My ...
362 views

I would like a hint for the following, more specifically, what strategy or approach should I take to prove the following? Problem: Let $P \geq 2$ be an integer. Define the recurrence $$p_n = p_{n-1} ... 2answers 60 views ### Non-homogeneous recurrence relation For the recurrence :$$ a_{n} = 3a_{n-1} - 2a_{n-2} + F(n) $$find the particular solution when F(n) is a)  2^{n}  b)  2^{n}(n+1)  c)  2^{n} + n+1  Try: I have just finished homogeneous ... 2answers 72 views ### f(n) = 2f(n-1) -f(n-2) + 1 find closed form by repeated substitution$$f(0)=af(1)=bf(n) = 2f(n-1) -f(n-2) + 1$$How can I begin repeated substitution with this? I'm confused because there are two f terms not sure how to sub for both of them. 2answers 146 views ### Find all polynomials p such that p(x^2)=p(x)p(x+1) Find all polynomials p such that$$ p(x^2)=p(x)p(x+1).$$The goal is to find a general formula for polynomials that satisfy the above equation. 2answers 38 views ### Solving recurrence relations of the form a_{n} = b a_{n-1}^2 + c I have a recurrence relation of the form a_{n} = b a_{n-1}^2 + c, where c \neq 0. Specifically, mine is a_{n} = \frac{1}{2} a_{n-1}^2 + \frac{1}{2}, with a_0 = \frac{1}{2}. How are these ... 1answer 21 views ### Irreflexivity in Relations Which relations are irreflexive? a) x + y = 0. b) x = ±y. c) x − y is a rational number. d) x = 2y. e) xy ≥ 0. f ) xy = 0. g) x = 1. h) x = 1 or y = 1. If a set is irreflexive when no ... 1answer 24 views ### How to find explicit form of recurrence relation with four variables for combinatorical value I want to know how many ways there are to choose l elements in order from a set with d elements, allowing repetition, such that no element appears more than 3 times. I've thought of the ... 2answers 73 views ### Solving recursion (Gambler's ruin) Let M_{i} denote the mean number of games until the gambler either goes broke or reaches a fortune of N, given that he starts with i = 0,1,\ldots,N. I have shown that M_{0} = M_{N} = 0 ... 0answers 36 views ### Recurrence Relations ... 1answer 36 views ### Counters on a Chessboard (BMO 2010/11) Isaac has a large supply of counters, and places one in each of the 1 \times 1 squares of an 8 \times 8 chessboard. Each counter is either red, white, or blue. A particular pattern of colored ... 0answers 21 views ### Algorithm for finding linear recurrent approximations to integer sequences Is there an algorithm for taking a sequence of integers and approximating a first part of it piecewise if need be with pieces like:$$ \text{ if } n = 2k, \\ a_n = a_{n-1} - a_{n-2} + 1 $$then, ... 1answer 33 views ### recursive function: non-recursive form possible? Can the following recursive function be converted to a non-recursive form?$$f(x,c,\ell)=\frac{c-c^\ell}{1-c}+(c-2)\sum \limits_{k=1}^{\ell-1}f(x,c,k)f(x,c,1)=cc= \text{constant}$$... 1answer 82 views ### Closed form solutions to a recursion relation Consider a following recursion relation of degree two: $$y_{n+1} = f_n \cdot y_n + g_n y_{n-1}$$ for n\ge 1 subject to y_1={\mathcal F}_1 and y_0={\mathcal F}_0. By ... 1answer 27 views ### What's the general term of the squence (U_n)_n such that U_n+\frac{1}{U_{n-1}}=2? [closed]$$ U_n+\frac{1}{U_{n-1}}=2 $$How we can find the general term of this sequence? 0answers 41 views ### How to solve recurrence T(n) = T(n/3) + T(2n/3) +n using Master Theorem I'm trying to solve the following recurrence using Master Theorem, but I'm not used to seeing recurrences with to terms ( i.e. T(n)) for the cost of operations. I'm pretty sure that a should be 1 and ... 1answer 22 views ### Solve the recurrence relation a_{k+2}-6a_{k+1}+9a_k=3(2^k)+7(3^k), k\geq 0, k_0=1,k_1=4. Solve the recurrence relation a_{k+2}-6a_{k+1}+9a_k=3(2^k)+7(3^k), k\geq 0, k_0=1,k_1=4. I know that I need a general solution of the form a_k=a^{(h)}_k+a^{(p)}_k, where the first term is a ... 4answers 69 views ### Finding the polynomials (or power series) p_n(x) such that 2\int x^ne^{x^2}dx = p_n(x) e^{x^2} By using integration by parts, one can obtain the following equation$$2\int x^ne^{x^2}dx=x^{n-1}e^{x^2}-(n-1)\int x^{n-2}e^{x^2}dx .$$A recursive formula for \int x^ne^{x^2}dx that works if ... 1answer 42 views ### How to get the Delannoy Number Generating Function The Delannoy path is a set of paths from (0, 0) to (m, n) using only steps (1, 0), (1, 1) or (0, 1). I know the generating function is \frac{1}{1-x-y-xy} So far Im given, D(x, y) = \sum_{m \geq ... 3answers 44 views ### Number of n-digit binary numbers such that no two zeroes are consecutive Let a_n denote the number of n-digit binary numbers such that no two zeroes are consecutive. Is a_{17}=a_{16}+a_{15}? Let a_n denote the number of n-digit binary numbers such that no ... 0answers 58 views ### Finite sum with three binomial coefficients I need to find a closed form expression, if there is one, of the following sum:$$\sum_{j=0}^m{n+1-k\choose j}{k-1\choose m-j}{A+2-k+m-j\choose m-j+2}$$where all parameters are integers, ~1\leq ... 2answers 89 views ### How to show that a_n : integer a_{n+1}=\frac{1+a_na_{n-1}}{a_{n-2}}(n\geq3), a_1=a_2=a_3=1 I would appreciate if somebody could help me with the following problem: Q: How to show that a_n : integer$$a_{n+1}=\frac{1+a_na_{n-1}}{a_{n-2}}(n\geq3), a_1=a_2=a_3=1$$2answers 18 views ### Recursion involving Piecewise Student C tries to define a function G: Z^{+}\rightarrow Z by the rule G(n) = \begin{cases} \ 1, & \text{if n is 1}\\ \ G(\frac{n}{2}), & \text{if n is even} \\[2ex] G(3n-2), ... 0answers 23 views ### Recurrence Solution does not satisfy base case Can someone tell me what am i doing wrong here ? My base case i.e. T(4)=12 ... 0answers 39 views ### Analytic formulas for recursive sequences of polynomials I have a sequence of polynomials \{ f_{m} \} with f_{m} \in \mathbb{Z}[x] that satisfies an order 2 linear recurrence relation. In particular, I have a polynomial g \in \mathbb{Z}[x] such that ... 0answers 63 views ### Asymptotics of the solution of G_n(t) = \text{const}, where G_n(t) = e^t (1 + r^{-1}(G_{n-1}(t) - 1))^{r}. Consider a sequence of functions (G_n(t)) on \Bbb{R} that satisfies the recurrence relation$$ G_0(t) = e^t, \qquad G_n(t) = e^t \left( 1 + \frac{G_{s-1}(t) - 1}{r} \right)^{r}. $$for some ... 3answers 50 views ### Solving recurrence T(n) = T(n-2) +2 \log(n) using the Substitution Method T(n) = T(n-2) +2 \log(n) if n>1 & 1 if n=1 So I start by substituting 3 times to get an idea about the pattern: T(n)=T(n-4) + 2 \log(n-2) + 2 \log n T(n)=T(n-6) + 2\log(n-4) + 2\log(n-2) + ... 1answer 104 views ### Greatest Common Divisor with Fibonacci Numbers [duplicate] Prove that for all integers n\geq 0:$$\gcd(F_{n+1},F_n)=1$$I am extremely lost. Please can some provide some hint or direction? Thank you so very much 0answers 39 views ### Proving that x_{n+1} = ax_{n}(1-x_{n}) converges when 1<a<3. I need some guidance for proving x_{n+1} = ax_{n}(1-x_{n}) converges when 1<a<3. What are some tips you guys could give me to help prove this point, without telling me how to do it? I'm ... 1answer 79 views ### How to show that all trajectories of the system approach a unique periodic solution? Consider an overdamped linear oscillator forced by a square wave. The system can be nondimensionalized to \dot{x}+x=F(t), where F(t) is a square wave of period T: F(t)=\begin{cases} +A, & ... 4answers 98 views ### Solving recurrence relation? Consider the recurrence relation a_1=8,a_n=6n^2+2n+a_{n−1}. Let a_{99}=K\times10^4 .The value of K is______ . My attempt : a_n=6n^2+2n+a_{n−1} =6n^2+2n+6(n−1)^2+2(n−1)+a_{n−2} ... 1answer 42 views ### Quadratic recurrence relation (from a math-contest) It's given the following quadratic relation:$$a_n = \frac{a_{n-1}^2+61}{a_{n-2}}$$Find a_{10}. Note that I can't use a calculator or a computer, instead I was wondering if there's a trick to find ... 1answer 23 views ### Initial condition for recurrence relation I have a question regarding the solution of this problem. The problem is: Suppose that we have n dollars to use to buy either orange juice for 1, milk for 2, or beer for 2, and the order in which we ... 0answers 49 views ### consider the function f(1) = 1, f(n) = \sum_{i = 1}^{n - 1}(if(i)) for n > 1 Consider the function f(1) = 1 f(n) = \sum_{i = 1}^{n - 1}(if(i)) for n > 1 Let A(n) be the worst-case number of scalar arithmetic operations (+,-,*,/) required by this function for ... 1answer 45 views ### Convert recursive formula to explicit formula using backtracking This is a question from the book Discrete Mathematical Structures by Bernard Kolman, Robert C. Busby and Sharon Cutler Ross. I want to find the explicit formula of the following recursive formula ... 2answers 64 views ### Ramanujan's infinitely nested radical clarification I was reading Wikipedia's article for nested radicals (link here), when I stumbled across Ramanujan's problem. I was following along fine until it got to the step where F(x+n) had to be simplified. ... 0answers 575 views ### Mirror algorithm for computing \pi and e - does it hint on some connection between them? Benoit Cloitre offered two 'mirror sequences', which allow to compute \pi and e in similar ways:$$u_{n+2}=u_{n+1}+\frac{u_n}{n}v_{n+2}=\frac{v_{n+1}}{n}+v_{n}u_1=v_1=0$$... 2answers 49 views ### Generating function to find the number of ways to put marbles in a basket Write a generating function for the number of ways to make a basket of n marbles, if you need to use at least one orange marble , an even number of yellow marbles, at most 2 green marbles, and any ... 0answers 15 views ### Inhomogeneous Legendre recurrence relation How can I find the particular solution to following recurrence relation for F_n(x,r)?:$$nF_n +(2n-1)xrF_{n-1}+(n-1)r^2F_{n-2}=1$$Withe initial values F_0=0, F_1=1. The corresponding ... 6answers 91 views ### Prove that the sequence: a_1 = 1, a_{n+1} =\sqrt{c+da_n} (when the real numbers c, d > 1) is converging and find it's limit I have a summarized solution but it's starts with proving that the sequence is bounded from above by c+d. How can I know that this sequence is bounded by c+d? I understand the proof by induction but ... 2answers 53 views ### Recurrence involving derivative I would like to get a closed form of A_n(x) if verifies the following recurrence relation$$A_n(x)=\frac{d}{dx}\left(\frac{A_{n-1}(x)}{a-\cos x}\right)\,\,\,\text{and}\,\,\,A_0(x)=1. Really I ...
Referring to Non linear recurrence relation? "The recurrence (2) then implies that $h_m=h_0+md$ for (m≥0)", What does $h_0$ refer to and how is it derived? From what I can see in equation(2), when ...