Deleting any list that contains a negative number

Question

We had another nice question in a student activity today.

The increasing sequence of positive integers $a_1,a_2,a_3,\ldots$ has the property that

$$ a_{n+2}=a_n+a_{n+1} \text{ for all } n\ge 1. $$

If $a_7=120$, find $a_8$. (Solution: $a_8=194$.)

I found the RecurrenceTable command and wrote:

seqs=Table[RecurrenceTable[{a[2 + n] == a[n] - a[1 + n], a[1] == 120, 
   a[2] == k}, a, {n, 1, 7}], {k, 1, 120}]

This produced a list of lists that are possible answers. How can I delete any list from seqs that contains a negative number? And if necessary, how can I delete any list from seqs that is not decreasing?

Also, if anyone else sees a nice way of solving this problem using Mathematica, I'd love to see your contribution.

Answer 1

Pick lists that don't contain negative number:

Pick[seqs, UnitStep @@@ seqs, 1]

{{120, 72, 48, 24, 24, 0, 24}, {120, 73, 47, 26, 21, 5, 16}, 
 {120, 74, 46, 28, 18, 10, 8}, {120, 75, 45, 30, 15, 15, 0}}

Pick non-increasing lists:

Pick[seqs, UnitStep @@@ -Differences /@ seqs, 1]

{{120, 74, 46, 28, 18, 10, 8}, {120, 75, 45, 30, 15, 15, 0}}

And here is another approach to solve the problem:

sol = RSolve[{a[2 + n] == a[n] - a[1 + n], a[1] == 120, a[2] == a2}, a, n][[1, 1, -1]]
Reduce[{GreaterEqual @@ sol /@ Range@7, sol@7 > 0}, a2, Integers]

a2 == 74

Answer 2

Candidate initial conditions:

mat = {{1, 1}, {1, 0}};
res = MatrixPower[mat, 7,{a, b}];
Reduce[res[[1]] == 120, {a, b}, Integers]

yields: C1 [Element] Integers && a == 2 + 13 C1 && b == 6 - 21 C1

fun[x_] := {2 + 13 x, 6 - 21 x}

The constraint of sequence of positive integers:

Reduce[Positive[fun[x]], x, Integers]

yields $x=0$ and is sufficient to guarantee and increasing sequence.

So, a[n_, v_] := (MatrixPower[mat, n,v][[1]],

a[8, fun[0]]

Yields 194.

and just for fun:

Manipulate[
 tab = Table[fun[j], {j, 0, p}];
 ListPlot[Transpose[Table[{j, a[j, #]} & /@ tab, {j, 0, 9}]], 
  Joined -> True, Epilog -> {Red, PointSize[0.02], Point[{7, 120}]}, 
  Frame -> True, 
  FrameLabel -> {"n", "\!\(\*SubscriptBox[\(a\), \(n\)]\)"}, 
  BaseStyle -> 12, GridLines -> {{8}, {194}}], {p, Range[5]}]

Answer 3

The following retains only Lists that are strictly decreasing and contain no negative elements.

Cases[seqs, {z1_, z2_, z3_, z4_, z5_, z6_, z7_} /; z1 > z2 > z3 > z4 > z5 > z6 > z7 > 0]
(* {{120, 74, 46, 28, 18, 10, 8}} *)

or, more succinctly (see comments below),

Cases[seqs, {z__} /; Greater[z, -1]]

Additionally, the second code block in the Answer by xzczd can be modified readily to select only strictly decreasing non-negative Lists.

Pick[seqs, UnitStep @@@ (-Differences /@ seqs - 1), 1]
(* {{120, 74, 46, 28, 18, 10, 8}} *)

There undoubtedly are other approaches.