# Tagged Questions

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

6 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 ?
55 views

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

34 views

### When is a recurrence the sum of the powers of the roots of a polynomial?

Newton's formula allows one to calculate the sum $S_n(P)$ of the $n$th powers of the roots of a given monic polynomial $P$ without finding the roots explicitly. (This works even when the roots ...
78 views

37 views

### How to solve this recurrence $T(n) = \log{n}*T(n/\log{n})+\sqrt{n}$

I tried substitution for $2^n$ or $2^{\log{n}}$ or even $2^{2^n}$ and it didn't work. Thanks! :)
28 views

In a recent problem I was working through, I came across the following recurrence relation: $$\text{K}_1(x,\ t;\ g) = 1,\quad x, t\in\Bbb{R}\quad g\in\text{C}^1 \\ \text{K}_{n+1}(x,\ t;\ g) = g'(t)\... 1answer 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 ... 3answers 35 views ### Trying to solve non-homogeneous linear recurrence relation with difficult non-homogeneous part I have the following recurrence relation that I'm trying to solve:$$f(n)=2f(n-1)-f(n-2)-2$$The homogeneous part is easy: The characteristic polynomial r^2-2r+r=0 has root r=1 with ... 0answers 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 ... 0answers 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} + 1k\geqslant 1$$I'm trying to convert a recurrence relationship for producing triangle square-numbers into a closed-form expression in terms of ... 1answer 41 views ### How to solve this recursion? If r>0 holds and recursion is given by T(r)=\alpha T(r^{1/\alpha})+\alpha r^{1/\alpha} where \alpha\geq 2 is fixed and assume T(r)=O(1) for r\leq1. What is T(r)? 4answers 84 views ### Closed form of recurrence relation F(n) = 2 + F(n-1) + F(n-2) I was figuring out an answer to the question, How many Boolean arrays of length n could be formed if there are to be no two falses in a row? I could see that it boils down to a Fibonacci ... 2answers 26 views ### Finding the generating function of a recurrence relation in dependence of a variable Given this inhomogeneous linear recurrence relation of 2nd order : F_n = F_{n-2} + a for n \geq 2 with F_1 = 1 and F_0 = 0 How do I find the generating function of this recurrence ... 0answers 9 views ### 2D recurrence relation Lately I encountered following DE:$$ x O^\alpha f\left(x\right) = f\left(x\right)-1 $$, where$$ O f\left(x\right) = x f'\left(x\right) + f\left(x\right) $$It can be solved using a solution to the ... 1answer 31 views ### Josephus problem: the renumbering method from Concrete Mathematics In Concrete Mathematics, Chapter 3, Section 3, an interesting method to solve the Josephus problem is discussed. The paragraphs below depict the method, which are extracted from the book: (Initially, ... 1answer 67 views ### a_{n+1} = (a_n+1)a+(a+1)a_n+2\sqrt{a(a+1)a_n(a_n+1)} \quad (n = 1,2,\ldots). Let a be a positive integer and \{a_n\} be defined by a_0 = 0 and$$a_{n+1} = (a_n+1)a+(a+1)a_n+2\sqrt{a(a+1)a_n(a_n+1)} \quad (n = 1,2,\ldots).$$Show that for each positive integer n, a_n ... 0answers 61 views ### Solving a non-standard linear recurrence [closed] Can you find an expression for the sequence (a_n) satisfying the following recurrence$$a_n = a_{n-1} + a_{n-2} + \sum_{i=3}^{n} 2\binom{n}{i}a_{n-i}$$for n \geq 3 where a_0 = 0, a_1 = 1, a_2 ... 0answers 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}? 0answers 37 views ### Proving that one sequence is greater than another using a recurrence inequality I'm trying to understand the proof of proposition 2 from All reductive p-adic groups are tame, Bernshtein. In the article there are given two sequences of functions \{{f_l}\}_{l=0}^\infty, \{{\... 1answer 32 views ### Using determinants to find a recursive sequence I am trying to compute a three diagonal determinant in order to find the recursive relation. Let \Delta_{n}=\begin{vmatrix} 11 & 3 & 0 & 0 & \dots & 0\\ 13 & 11 & 3 &... 0answers 44 views ### Solving recurrence relation a_n=1 + \sum\limits_{i=1}^{n-1}ia_{n-i} with a_1=1 Consider the recurrence relation$$a_n=1 + \sum_{i=1}^{n-1}ia_{n-i}$$with initial term a_1=1. What is a_n? I tried to guess some closed formula from the first 6 terms, which are 1, 2, 5, ... 1answer 23 views ### Solving Recurrence Relations with generating functions when the variable is in the function. I'm studying for a midterm and couldn't figure out these three recurrences that I came across: i_{n+1}=2ni_n+2i_n+2 with initial condition i_0=1 j_{n+1}=3j_n+1 with initial condition j_1=1 ... 2answers 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. ... 1answer 21 views ### 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 ... 2answers 37 views ### how many sequences above 1,2,3,4,5,6,7 that don't contain odd couples I got stucked a little with this question. would appreciate your help. the question is "find a recursive relation that counts how many sequences of order n above {1,2,3,4,5,6,7} that don't contain ... 3answers 69 views ### 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. 1answer 71 views ### second-order difference equation with variable coefficients ax_{n+1}-(n+1+a)x_n+nx_{n-1}=-n The equation is: ax_{n+1}-(n+1+a)x_n+nx_{n-1}=-n, where a is a constant and 0<a<1. Any ideas on how to solve it? May be the z-transform is useful? Thank you! Using the difference operator ... 0answers 90 views ### Solutions to recurrence relations Consider functions s_{m},c_{m},d_{m} defined by the following recurrence relations$$s_{1}=nc_{1}=sd_{1}=0s_{2}=nc_{2}=s-nd_{2}=d$$s,n, d are integers. If c_{m}>... 4answers 57 views ### Prove for all  n\in \mathbb{N}  ,n ≥ 1, a(n) is odd. Prove for all n\in\mathbb{N}\backslash \{0\}, a(n) is odd. Consider the sequence defined as followed: a(1)= 1 a(2)= 3,where n \in \mathbb{N}$$a(n)=a(n-2)+2a(n-1), n ≥3$$Conjecture: ... 1answer 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{... 2answers 41 views ### How can I solve this exponential recurrence relation? Does anyone know how to solve a_{n+1}=1-Ce^{-a_n} explicitly for a_n in terms of n and a_0, where C is constant? 3answers 98 views ### Recurrence relation solution a_{n}=\frac{a_{n-1}}{a_{n-1}-a_{n-2}} I want to find the analytic form of the recurrence relation$$a_{n}=\frac{a_{n-1}}{a_{n-1}-a_{n-2}},\,a_{1}=2,\,a_{2}=1 $$but when looking at the results they seem chaotic. Is it possible that it ... 1answer 40 views ### I need a common term for a recursive sequence Some days ago, I made a question here about a common term for recursive sequence. I gained very good solutions. Thanks again. Today, I was thinking of a general case which is given below. Assume p ... 5answers 56 views ### Solving a_n = a_{n-1} + 7n for n\ge1 and a_0 = 4 First, I found the homogeneous solution:$$r^n - r^{n-1} = 0\Rightarrow r = 1$$So the homogeneous solution is of the form:$$c(1)^n = c Then, to find a particular solution, I "guessed" the ...
Let $a= \frac{1+\sqrt{5}}{2}$ and $b= \frac{1-\sqrt{5}}{2}$. Prove that for all $c,d \in \mathbb{N}$ that $g_n = ca^n + db^n$ satisfies $g_{n+2} = g_{n+1} + g_{n}$ for all $n\in \mathbb{N}$. I'm ...
Lucas recurrence relation is defined as: $V_n = PV_{n-1} – QV_{n-2}$; for $V_0 = 2; V_1 = P$ Here $P$ is positive integer and $Q = {-1, 1}$ or may be $+1$ or $-1$ A Fibonacci Pseudo prime with ...