How can I rewrite this with NestList or FoldList?

Question

The original code used For:

{x, y} = {1, 1};
For[i = 0, i < 5, i++,
  x = x + 2 y;
  y = y + 2 x;
  Print[{x, y}]
  ];
Clear["`*"]

I am trying to use NestList to replace For, but the result is not as I expected. How can I rewrite it?

func[{x_, y_}] := {x + 2 y, y + 2 x};
NestList[func, {1, 1}, 5]

Answer 1

The problem is that you forget that you assign something to x and use this!

func[{x_, y_}] := Module[{xx = x + 2 y}, {xx, y + 2 xx}];
NestList[func, {1, 1}, 5]

But when you think about this short snip of code a bit longer, then you see the following: First you set x = x + 2 y and then you use this value in the next line. Basically, we can show this by simple replacements. We start with the {x,y} in the Print statement and do the calculation backwards:

{x,y}
%/.y->y+2x
%/.x->x+2y
ExpandAll[%]
(*
Out[56]= {x,y}
Out[57]= {x, 2x+y}
Out[58]= {x+2y, y+2(x+2y)}
Out[59]= {x+2y, 2x+5y}
*)

The last output shows exactly what Artes used. What you could notice here is, that this simple linear transformation can easily be converted into matrix form

{{1, 2}, {2, 5}}.{x,y}
(* {x + 2 y, 2 x + 5 y} *)

With this, you can write your NestList, which is equivalent to the function of Artes very nicely

NestList[{{1, 2}, {2, 5}}.# &, {1, 1}, 5]

Answer 2

Without Module :

f[{x_, y_}] := {x + 2 y, 2 x + 5 y}
NestList[ f, {1, 1}, 5]

 {{1, 1}, {3, 7}, {17, 41}, {99, 239}, {577, 1393}, {3363, 8119}}    

or exactly

NestList[f, {1, 1}, 5] // Rest // Column

Module is not recommended when we encounter a long list (or deep nesting) see e.g. Why modules with no variables ?.

Answer 3

In fact, even NestList[] is not needed, since Mathematica has MatrixPower[]:

NestList[{{1, 2}, {2, 5}}.# &, {1, 1}, 5]
   {{1, 1}, {3, 7}, {17, 41}, {99, 239}, {577, 1393}, {3363, 8119}}

Table[MatrixPower[{{1, 2}, {2, 5}}, k, {1, 1}], {k, 0, 5}]
   {{1, 1}, {3, 7}, {17, 41}, {99, 239}, {577, 1393}, {3363, 8119}}

MatrixPower[] can even be used to obtain a nice closed form for your iterates:

c[k_] = FullSimplify[MatrixPower[{{1, 2}, {2, 5}}, k, {1, 1}]]
   {1/2 ((3 - 2 Sqrt[2])^k + (3 + 2 Sqrt[2])^k), 
    1/2 (-(3 - 2 Sqrt[2])^k (-1 + Sqrt[2]) + (1 + Sqrt[2]) (3 + 2 Sqrt[2])^k)}

though this closed form does not automatically produce integers for integer argument, unless given some assistance:

c /@ Range[0, 5] // RootReduce
   {{1, 1}, {3, 7}, {17, 41}, {99, 239}, {577, 1393}, {3363, 8119}}