Tagged Questions
1
vote
2answers
82 views
Need some help with this recurrence equation
I'm self studying from a book I bought to learn more about algorithms and I've been trying most of the exercises in that book, so this is not a homework. Anyways, the relation I'm trying to solve is
...
1
vote
1answer
96 views
Alternative solutions to $n^2+n = k^2+k + 2kn$
Consider this equation:
$n^2+n = k^2+k + 2kn$
I want to find the set of non-negative integer n,k that satisfies the equation.
I tried to write $n$ as $k$ by solving the equation with $n$ as root ...
9
votes
2answers
85 views
Proving that $a_n$ is an integer for every $n$
For every $k\ge1$ integer number if we define the sequence : $a_1,a_2,a_3,...,$ in the form of :$$a_1=2$$
$$a_{n+1}=ka_n+\sqrt{(k^2-1)(a^2_n-4)}$$
For every $n=1,2,3,....$ how to prove that $a_n$ is ...
2
votes
2answers
69 views
Twice a triangle is triangle
The question is to prove that there are infinitely many triangular numbers $T_n$ where $2 \times T_n$ is also a triangular number, and give the first few as an example.
My attempt:
$$2 \cdot {x(x+1) ...
3
votes
1answer
61 views
$ n $ lines intersections
As we all know, $ n $ lines which are not coincident may have some intersection points in an Euclid plane. And we define the set of the number of intersection points $ n $ lines can form is $ ...
3
votes
5answers
157 views
How to create a generating function / closed form from this recurrence?
Let $f_n$ = $f_{n-1} + n + 6$ where $f_0 = 0$.
I know $f_n = \frac{n^2+13n}{2}$ but I want to pretend I don't know this. How do I correctly turn this into a generating function / derive the closed ...
1
vote
1answer
50 views
Show that Fermat number $F_n$ and its index $n$ are coprime.
I want to show that $\gcd(F_n,n)=1$, where $F_n=2^{2^n}+1$. How to prove this?
I can show that that $\gcd(F_n, F_m)=1$ for any natural $n$ and $m$, and that $F_{n+1}=(F_n)^2-2F_n+2=F_0\dots ...
2
votes
2answers
103 views
How do you find the closed form of these recurrence relations?
I found these two recurrence relations in an old textbook and was hoping someone could show me how to solve them for their closed form. If not, a final answer would also be appreciated, as it helps ...
4
votes
2answers
111 views
Does this problem have a name?
Recently our lecturer told us that it is an unsolved mathematical problem if the following while loop aka iteration ever terminates. Unfortunately I forgot to ask him what it is called. If someone ...
2
votes
6answers
267 views
I know that, $S_{2n}+4S_{n}=n(2n+1)^2$. Is there a way to find $S_{2n}$ or $S_{n}$ by some mathematical process with just this one expression?
$S_{2n}+4S_{n}=n(2n+1)^2$, where $S_{2n}$ is the Sum of the squares of the first $2n$ natural numbers, $S_{n}$ is the Sum of the squares of the first $n$ natural numbers.
when, $n=2$
...
10
votes
1answer
242 views
Why do the Fibonacci numbers recycle these formulas?
The Fibonacci numbers $F_n = 0, 1, 1, 2, 3, 5, 8, 13, \dots$
obey the following recurrence relations,
$ \begin{aligned}
&F_{n}-\;F_{n-1}-F_{n-2} = 0\\[1.5mm]
&F_{n-1}^3-F_{n}^3-F_{n+1}^3 = ...
17
votes
3answers
814 views
Self-avoiding walk on $\mathbb{Z}$
How many sequences $a_1,a_2,a_3,\dotsc$, satisfy:
i) $a_1=0$
ii) ($a_{n+1}=a_n-n$ or $a_{n+1}=a_n+n$)
iii) $a_i\neq a_j$ for $i\neq j$
iiii) $\mathbb{Z}=\{a_i\}_{i>0}$
Are the two alternating ...
2
votes
0answers
162 views
Bell-like recurrence
Let
$$A(n)=\sum_{k=0}^{n-1}\binom{n}{k}A(k)+n!,\quad A(0)=1$$
$$B(n)=\sum_{k=0}^{n-1}\binom{n}{k}B(k)-n!-n!\sum_{k=1}^{n}\frac{1}{k!},\quad B(0)=-1.$$
I'm interested in computing $S(n)=A(n)+B(n)$ ...
3
votes
0answers
56 views
Properties preserved under the “reversal” of a recurrence equation
Consider the recurrence equation
$u_n = f(u_{n-1},\ldots, u_{n-k})\;,$
defined for $n=0,1,2\ldots$.
If this is a linear recurrence and the coefficient function on $u_{n-k}$ is nonzero in ...
3
votes
0answers
148 views
Is this a recurrence for the Mertens function plus 2?
If we define a symmetric array:
$$T(1,1)=3,\; T(1,2)=2,\; T(2,1)=2$$
$$T(1,k)=\frac{-T(n,k-1)-\sum\limits_{i=2}^{k-1}T(i,k)}{k+1}+T(n,k-1)$$
$$ ...
8
votes
1answer
119 views
Prove that a holonomic (p-recursive) difference equation returns only integral values
Consider the recurrence given by
$(n+1)^2 a_{n+1} = (9n^2+9n+3)a_n-27n^2 a_{n-1}$
$a_0 = 1, a_1 = 3$.
Clearly, $a_n$ is rational, but unexpectedly, the recurrence seems to output only integral ...
6
votes
1answer
209 views
Common terms in general Fibonacci sequences
Mathworld notes that "The Fibonacci and Lucas numbers have no common terms except 1 and 3," where the Fibonacci and Lucas numbers are defined by the recurrence relation $a_n=a_{n-1}+a_{n-2}$. For ...
7
votes
1answer
163 views
Diagonal of the double sequence $(n+1)v_{h,n+1}-(2h+1)v_{h,n}-nv_{h,n-1}=0$
Update: it is not possible to reply to this question without additional information.
My comment below: "I have to agree with you that one "cannot derive (2) from (1) alone". Now it seems to me that ...
3
votes
2answers
202 views
Recurrence relation for $a_{n}$ where $6a_{n}$ and $10a_{n}$ are both triangular
According A180926, the elements of the set
{$a:\exists m,n|60a=5n^2+5n=3m^2+3m$} satisfy the following recurrence relation:
$$a_{n}=\frac{62a_{n-1}+1+\sqrt{(48a_{n-1}+1)(80a_{n-1}+1)}}{2}$$
...
