3
$\begingroup$

Find the closed form of the following sequence of integers: $a_1=x>0$, $$a_n=\left\lfloor\dfrac{(n+2)a_{n-1}-2}{n}\right\rfloor, n \ge 2$$

I calculated a few terms, and $a_1=x$, $a_2=2x-1$, $a_3=2x-6+\lfloor \frac{4x}{3}\rfloor$. However, the terms get really ugly after this. Then, I tried to find the closed form for certain values of $x$. For example, when $x=5$, I found that consecutive terms differ by $4$, $5$, $6$..., so the closed form is $a_n=\frac{n^2}{2}+\frac{5n}{2}+2$. Firstly, I'm not sure how to prove this, and secondly, this method does not always work for other values of $x$, so I'm not sure what to do next.

Thanks in advance!

$\endgroup$
4
  • 2
    $\begingroup$ Following the recurrence relation I think one gets $a_3=\left\lfloor\frac{5}{3}(2x-1) - \frac{2}{3} \right\rfloor =\left\lfloor\frac{10x}{3} - \frac{7}{3} \right\rfloor $. $\endgroup$ Jul 13, 2023 at 3:49
  • 1
    $\begingroup$ There is always a unique solution to any initial value problem involving a recurrence relation and an initial condition. So, if there is a closed form solution and one can guess it. You can prove it is the solution by checking it satisfies the recurrence relation. ("Guess and check.") $\endgroup$ Jul 13, 2023 at 3:53
  • $\begingroup$ Yes, but I am having trouble generalizing the solution for different initial values. I have found the first few closed forms, but they don't seen to follow a clear pattern. $\endgroup$ Jul 13, 2023 at 4:05
  • $\begingroup$ hmmmmm . . . your solution does satisfy the recurrence relation and the initial condition $a_1 = 5$. It is not clear to me how to modify the solution if one changes the initial condition. I will have to think on it. $\endgroup$ Jul 13, 2023 at 4:41

1 Answer 1

3
$\begingroup$

I'm assuming that one only needs to consider integer values for $x$ as the succeeding terms will end up being integers. (Update: I'm wrong about only needing to assume that one needs to consider integers. It appears that if the fractional part of $x$ is greater than or equal to 1/2, then a different sequence is generated.)

One can generate sequences for several initial values and look up those sequences at https://oeis.org/. (One finds the same sequence that you found for $x=5$.) Then maybe an overall closed-form solution will become apparent.

Alternatively, one can speed up that process with software. Here I'm using Mathematica.

f[a1_] := Module[{t}, a = {a1};
  Do[a = Join[a, {Floor[((i + 2) a[[i - 1]] - 2)/i]}], {i, 2, 20}];
  FullSimplify[FindSequenceFunction[a, n], 
    Assumptions -> n \[Element] PositiveIntegers] // Expand]

Table[{i, f[i]}, {i, 1, 20}] // TableForm

sequences in closed form

There certainly appears to be a consistent pattern here with one pattern for multiples of 3 and another for the remaining values.

For integer values of $x$ that are multiples of 3 the general sequence is generated by

$$a(n)=\frac{1}{24} \left(4 n (n+3) x+3 \left((-1)^n+7\right)-6 n (n+2)+8 x\right)$$

Update:

From the comment by @JoshuaWang a simplification can be made. For non-negative integer values of $k$ the following gives the sequences for $x=3k$, $x=3k+1$, and $x=3k+2$:

$$a_{3k}=\frac{7+(-1)^n}{8}+k+\frac{(3k-1)n}{2}+\frac{(k-1/2)n^2}{2}$$ $$a_{3k+1}=1+k+\frac{3kn}{2}+\frac{k n^2}{2}$$ $$a_{3k+2}=1+k+\frac{(3k+2)n}{2}+\frac{k n^2}{2}$$

2nd update: Values of $x$ where the fractional part is not zero

From trying various starting values it appears that values of $x$ where the fractional part (denoted by $\{x\}$) is less than 1/2 results in the same sequence (for $n \geq 2$) as that of the floor of $x$ ($\lfloor x \rfloor$) which is described previously.

Also, for those values of $x$ with a fractional part greater than or equal to 1/2 and less than 1 ($1/2 \leq \{x\} <1$), the same sequence results. In other words, $x=3.57$ and $x=3.999$ result in the same sequence.

Here is the evidence (rather than proof) I base that on:

f2[a1_] := Module[{t}, a = {a1};
  Do[a = Join[a, {Floor[((i + 2) a[[i - 1]] - 2)/i]}], {i, 2, 20}];
  ((FullSimplify[FindSequenceFunction[a[[2 ;;]], n + 1], 
  Assumptions -> n \[Element] PositiveIntegers] // Expand))]
    
Table[{x, f2[x]}, {x, {5.5, 5.6, 5.7, 5.8, 5.9, 11.5, 11.6, 11.7, 11.8,  11.9}}] // TableForm

Evidence of unchanging resulting sequence when fractional values are between 1/2 and 1

We can generate a series of sequences for various starting values to see if a pattern exists similar to before:

Table[{x, f2[x]}, {x, Range[2.8, 20.8]}] // TableForm

Table of sequences for x=2.8, 3.8, 4.8,..., 20.8

Note that we can rewrite the sine and cosine terms as follows:

$$\cos(\frac{2n\pi}{3})=3 \left\lfloor \frac{n}{3}\right\rfloor -3 \left\lfloor \frac{n+2}{3}\right\rfloor +2$$

$$\sqrt{3}\sin(\frac{2n\pi}{3})=\frac{3}{2} \left(n-3 \left\lfloor \frac{n+1}{3}\right\rfloor \right)$$

$\endgroup$
4
  • 2
    $\begingroup$ It seems like $\displaystyle a_{3k+1} = 1 + k +\frac{3kn}{2}+\frac{kn^{2}}{2}$ and $\displaystyle a_{3k+2} = 1 + k + \frac{(3k+2)n}{2} + \frac{kn^{2}}{2}$. $\endgroup$ Jul 13, 2023 at 5:52
  • $\begingroup$ @JoshuaWang Thanks. That looks a lot cleaner. I'll take a closer look tomorrow morning. $\endgroup$
    – JimB
    Jul 13, 2023 at 6:05
  • $\begingroup$ Sorry, I ran out of time today to figure out the general formulas for when the fractional part of $x$ is greater than or equal to 1/2 and less than 1. Maybe in the next few days. $\endgroup$
    – JimB
    Jul 14, 2023 at 3:21
  • $\begingroup$ It seems the conjecture (guess) is now that for $x\equiv 0, 1, 2$ (mod $3$) the closed form of the solution is: \begin{align*} a_{1}=3k\; &\Rightarrow &a_{n} &=\frac{7+(-1)^n}{8}+k+\frac{(3k-1)n}{2}+\frac{(k-1/2)n^2}{2} \\ a_{1}=3k+1 &\Rightarrow &a_{n} &=1+k+\frac{3kn}{2}+\frac{k n^2}{2}\\ a_{1}=3k+2 &\Rightarrow &a_{n} &=1+k+\frac{(3k+2)n}{2}+\frac{k n^2}{2} \end{align*} The next step should be to verify (check) that these formulas actually do satisfy the recurrence relation (not just the first several terms) as well as the initial condition. If that checks out, we will be done! $\endgroup$ Jul 15, 2023 at 21:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .