7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ DeleteCases[seqs, {___, _?Negative, ___}, {1}] $\endgroup$ – Mike Honeychurch Nov 14 '15 at 5:51
  • 1
    $\begingroup$ Cases[seq, {_?NonNegative ..}] $\endgroup$ – Bob Hanlon Nov 14 '15 at 15:12
  • $\begingroup$ 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. $\endgroup$ – halirutan Dec 3 '15 at 4:11
5
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Nov 14 '15 at 17:34
  • $\begingroup$ @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 :) $\endgroup$ – xzczd Nov 14 '15 at 18:04
4
$\begingroup$

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]}]

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Use the "action" form instead: MatrixPower[mat, 7, {a, b}] $\endgroup$ – J. M. will be back soon Nov 14 '15 at 7:03
  • $\begingroup$ @J.M. Thank you I will edit when I get time. $\endgroup$ – ubpdqn Nov 14 '15 at 7:15
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Actually the first piece of code can be shortened to Cases[seqs, {z__} /; Greater[z, 0]] :) $\endgroup$ – xzczd Nov 14 '15 at 6:39
  • $\begingroup$ @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. $\endgroup$ – bbgodfrey Nov 14 '15 at 6:50
  • 1
    $\begingroup$ To be more precise, the criterion of OP's question is non-negative, while the original problem requires the sequence to be positive 囧. $\endgroup$ – xzczd Nov 14 '15 at 6:55
  • 2
    $\begingroup$ The infix notation for Greater works with sequences too: Cases[seqs, {z__} /; z > 0] $\endgroup$ – Simon Woods Nov 14 '15 at 16:27

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.