0
$\begingroup$

Update: I made a mistake when posting this question - the recursive definition in $\text{(A)}$ was defined with

$\tag A A_{n+1} = (n-1)A_n + 2B_n \quad \quad \text{ERROR}$

and has now been corrected.

I checked and the recursion now agrees with the solution to the motivating problem linked to below.

The prior question was well founded and had two answers, with Calvin Lin solving it. Olivier Roche supplied hints using matrix methods.

I know I could have posted a new question, but figured this edit made the most sense.


Define $A_4 = 0$ and $B_4 = 2$.

For $n \ge 4$ define

$\tag A A_{n+1} = (n-1)A_n + 4B_n$

and

$\tag B B_{n+1} = (n-2) B_n$

Find an explicit formula in $n$ to represent the sum $A_n + B_n$ for $n \ge 5$.

My Work

I answered a combinatorial question on this site and wanted to use this method, but I'm not sure how to proceed. Using a combinatorial argument I verified the recursion holds, and want to apply the appropriate techniques to get the answer in a different way.

$\endgroup$
4
  • $\begingroup$ You can solve for $B_n$ first to get $$B_n = 2(n - 3)!$$ then use it to get $$A_n = 2(n - 4)(n - 3)!$$. The sum you want is just add them both. $\endgroup$
    – Azlif
    Nov 13 '19 at 15:55
  • $\begingroup$ @Azlif Guess this is really simple. I had the 'first' part but how does that give you $A_n$? (must be staring me in the face) $\endgroup$ Nov 13 '19 at 15:59
  • 1
    $\begingroup$ @CopyPasteIt One way is to prove via induction. Did you want a method that used a combinatorial approach? $\endgroup$
    – Calvin Lin
    Nov 13 '19 at 16:03
  • $\begingroup$ @CalvinLin A combinatorial approach is of interest, provided we don't start seating people at a table. It would be interesting to see how you might 'guess' that $A_n = 2(n - 4)(n - 3)!$ (heuristic/intuition/simplification/conjecture) so that you can justify induction. $\endgroup$ Nov 13 '19 at 16:14
2
$\begingroup$

Write $X_n := \begin{pmatrix} A_n \\ B_n \end{pmatrix}$ and $M_n := \begin{pmatrix} (n-1) & \mathbf{4} \\ 0 & (n-2) \end{pmatrix}$, this allows you to sum up the recurrence relation as : $$\boxed{X_{n+1} = M_n X_n}$$

In other words, one has $X_n = (\prod_{k=4}^n M_k)X_4 $. Your goal is now to express $P_n :=(\prod_{k=4}^n M_k)$ with a closed formula.

conjecture1 (wrong) for $n\geqslant 5$, one has $$P_n = \begin{pmatrix} (n-1)! & n(n-1)-12\\ 0 & (n-2)! \end{pmatrix} $$

New try (one should be able to solve the problem without knowing $\star$) :

conjecture2 for $n\geqslant 4$, $P_n$ is of the form $$P_n = \begin{pmatrix} \frac{(n-1)!}{2} & \star\\ 0 & (n-2)! \end{pmatrix} $$

$\endgroup$
9
  • $\begingroup$ I think OP's goal is to "use this combinatorial method", as opposed to "prove this recurrence relation property", though his new comment suggests it doesn't matter. @CopyPasteIt, can you clarify? $\endgroup$
    – Calvin Lin
    Nov 13 '19 at 16:01
  • $\begingroup$ @CalvinLin This is the type of answer I wanted to see. For some reason, when I see these type of problems, I can't find a 'theory handle' and just 'turn the crank'. This looks like the way to go, replacing two recursions with one 'matrix recursion' (+1). $\endgroup$ Nov 13 '19 at 16:05
  • $\begingroup$ If so, one approach is take is to calculate initial terms of the sequence, and then try to guess what the pattern is. Eg. I obtained OEIS A052582, which has the formula $2n\times n!$ (with some offsets). $\endgroup$
    – Calvin Lin
    Nov 13 '19 at 16:06
  • $\begingroup$ @CopyPasteIt If you can prove the conjecture above, you're done. Feel free to ask why I conjectured this. $\endgroup$ Nov 13 '19 at 16:14
  • $\begingroup$ @OlivierRoche Thanks - looks like fun and can now legitimately proceed with induction; see math.stackexchange.com/questions/3434096/… $\endgroup$ Nov 13 '19 at 16:17
1
$\begingroup$

By looking at initial terms and using induction, we can conclude that $A_n + B_n = 2 \times (n-3) \times (n-3)!$, $A_n = 2(n-4)(n-3)!$, $B_n = 2(n-3)!$.

Here is a combinatorial approach, but it is very contrived.

For a permutation $ \rho \in S_{n-2}$, count the number of pairs $(a_i, a_{i+1})$ such that $\rho(a_i ) - \rho (a_{i+1} $ are consecutive integers.
There are $n-3$ pairs of consecutive integers, and they are consecutive in $2\times (n-3)!$ ways, which means that there are a total of $2\times (n-3) \times (n-3)!$ such pairs.

Alternatively, let $B_n$ be the number of ways that a permutation of $S_{n-2}$ has "1,2" consecutive. Given any way for $B_n$, there are $n-2$ places we can insert the value $n-1$ in the permutation to obtain a way for $B_{n+1}$.
This is clearly a bijection so $B_{n+1} = (n-2) B_n$.
We can verify that $B_4 = 2$.

Let $A_n$ be the number of ways that a permutation of $S_{n-2}$ has "2,3" or "3,4", or ..., or "$n-3, n-2$" consecutive, counted with duplicity.
We have $A_n = (n-4) B_n$ by counting the number of pairs.
Hence $A_{n+1} = (n-3) B_{n+1} = (n-3) (n-2) B_n = (n-1)(n-4)B_n + 2B_n = (n-1)A_{n} + 2B_n$.
We can verify that $A_4 = 0$.

Hence, $A_n+ B_n = 2 \times (n-3) \times (n-3)!$.

$\endgroup$
1
$\begingroup$

Using Olivier Roche matrix technique, we define for $n \ge 4$

$$P_n = \begin{pmatrix} \frac{(n-1)!}{2} & p_n\\ 0 & (n-2)! \end{pmatrix} $$

where $p_n$ is, to start with, unknown, but $p_4 = 4$.

Set

$$M_{n+1} = \begin{pmatrix} n & 4\\ 0 & n-1 \end{pmatrix} $$

Multiplying $M_{n+1} \circ P_n$ to get $P_{n+1}$ we conclude that

$\tag 1 p_{n+1} = n p_n + 4 \, (n-2)!$

Handing this off to wolframalpha, the recurrence equation solution is given by

$\quad p_n = \bigr ( (c_1 + 4) n - c_1 - 8 \bigr ) Γ(n - 1) \quad \text{ (where } c_1 \text{ is an arbitrary parameter)}$

We can solve for $c_1$ knowing that $p_4 = 4$ and find that $c_1 = -2$.

So for $n \ge 4$ we can write

$\tag 2 p_n = 2 (n-3) \, (n-2)!$

By applying the matrix $P_n$ to the vector

$$ \begin{bmatrix} 0 \\ 2 \end{bmatrix} $$

we conclude that, for $n \ge 4$,

$\quad A_{n+1} = 2 * p_n = 4 (n-3) \, (n-2)!$

and

$\quad B_{n+1} = 2 * (n-2)!$

$\endgroup$
2
  • $\begingroup$ How did you use the $\Gamma$ function to solve the recurrence, please? $\endgroup$ Nov 14 '19 at 14:20
  • $\begingroup$ I just handed off the recursion to Wolfram that solved it. In the solution you get $\Gamma(n-1)$ . I figured that it is a class of recursions where $\Gamma$ comes into play. $\endgroup$ Nov 14 '19 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.