# Deleting any list that contains a negative number

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 == 120,
a == 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.

• DeleteCases[seqs, {___, _?Negative, ___}, {1}] Nov 14 '15 at 5:51
• Cases[seq, {_?NonNegative ..}] Nov 14 '15 at 15:12
• I'm not sure, why this old question popped up, but I just saw it now. You are aware that your problem can be solved completely analytically without using any numerical calculations? If I'm not completely mistaken, you can give conditions how to create only positive sequences. Dec 3 '15 at 4:11

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 == 120, a == a2}, a, n][[1, 1, -1]]
Reduce[{GreaterEqual @@ sol /@ Range@7, sol@7 > 0}, a2, Integers]

a2 == 74

• I understand this: UnitStep[{120, 120, 0, 120, -120, 240, -360}], which gives this: {1, 1, 1, 1, 0, 1, 0}. But I don't understand UnitStep @@@ seqs, which gives a list of zeros and four ones. I looked up @@@ in the documentation and read f @@@ expr replaces heads at level 1 of expr by f. OK, so why does UnitStep @@ {120, 120, 0, 120, -120, 240, -360} return just a zero and why does UnitStep @@ {120, 75, 45, 30, 15, 15, 0} just return a 1. Nov 14 '15 at 17:34
• @David Because UnitStep owns two kinds of syntax, UnitStep[x1, x2, ...] represents the multidimensional unit step function which is 1 only if none of the $x_i$ are negative :) Nov 14 '15 at 18:04

Candidate initial conditions:

mat = {{1, 1}, {1, 0}};
res = MatrixPower[mat, 7,{a, b}];
Reduce[res[] == 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][],

a[8, fun]


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}] • Use the "action" form instead: MatrixPower[mat, 7, {a, b}] Nov 14 '15 at 7:03
• @J.M. Thank you I will edit when I get time. Nov 14 '15 at 7:15

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.

• Actually the first piece of code can be shortened to Cases[seqs, {z__} /; Greater[z, 0]] :) Nov 14 '15 at 6:39
• @xzczd A capability I did not know. Thanks. Probably, should be Cases[seqs, {z__} /; Greater[z, -1]], though, because the question's criterion is non-negative. Nov 14 '15 at 6:50
• To be more precise, the criterion of OP's question is non-negative, while the original problem requires the sequence to be positive 囧. Nov 14 '15 at 6:55
• The infix notation for Greater works with sequences too: Cases[seqs, {z__} /; z > 0] Nov 14 '15 at 16:27