LinearRecurrence[{1, 0, 1}, {4, 2, 10}, 100]
{4, 2, 10, 14, 16, 26, 40, 56, 82, 122, 178, 260, 382, 560, 820, 1202, 1762, 2582, 3784, 5546, 8128, 11912, 17458, 25586, 37498, 54956, 80542, 118040, 172996, 253538, 371578, 544574, 798112, 1169690, 1714264,
2512376, 3682066, 5396330, 7908706, 11590772, 16987102, 24895808, 36486580, 53473682, 78369490, 114856070, 168329752, 246699242, 361555312, 529885064, 776584306, 1138139618, 1668024682, 2444608988,
3582748606, 5250773288, 7695382276, 11278130882, 16528904170, 24224286446, 35502417328, 52031321498, 76255607944, 111758025272, 163789346770, 240044954714, 351802979986, 515592326756, 755637281470,
1107440261456, 1623032588212, 2378669869682, 3486110131138, 5109142719350, 7487812589032, 10973922720170, 16083065439520, 23570878028552, 34544800748722, 50627866188242, 74198744216794,
108743544965516, 159371411153758, 233570155370552, 342313700336068, 501685111489826, 735255266860378, 1077568967196446, 1579254078686272, 2314509345546650, 3392078312743096, 4971332391429368,
7285841736976018, 10677920049719114, 15649252441148482, 22935094178124500, 33613014227843614, 49262266668992096, 72197360847116596, 105810375074960210}
$y(n+3)=y(n+2)+y(n)+2+ (n-1)\sin\left(\frac{\pin}{2}\right),y(1)=4,y(2)=2,y(3)=6$
来一个矩阵快速幂,O(lgn)复杂度的代码.
Block[{n = 10000, m}, m = DiagonalMatrix, -1]; m[] = {2, -3, 5, -4, 4, -3, 1, -1};
Last . Transpose[{36, 22, 16, 12, 6, 2, 4, 2}]]]