{"entities":{"Q1592813":{"pageid":1603553,"ns":120,"title":"Item:Q1592813","lastrevid":67990755,"modified":"2026-04-12T20:42:14Z","type":"item","id":"Q1592813","labels":{"en":{"language":"en","value":"Divide-and-conquer recurrences -- classification of asymptotics"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1556600"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1592813$EA4FE176-53C5-4396-9AEA-7636E8533B7C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"415571f362a4c82d37af50e5c72e15255030eefb","datavalue":{"value":{"text":"Divide-and-conquer recurrences -- classification of asymptotics","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1592813$D00CABFB-FD40-4291-BE3D-A03CD24C8A00","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8910db0213cb1ef3799c4dc08913831087c389cf","datavalue":{"value":"0986.39010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1592813$904F2D4B-0AFF-41DD-AC5E-E2BD0A73BFAA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"548e41b95381cd7afc1110de598da4745046286c","datavalue":{"value":"10.1007/PL00000132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1592813$507C3B7B-D5C2-4CC2-808C-3FF682F08717","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"115f46af7c072c5c66bc874f6856fbcd544de926","datavalue":{"value":{"entity-type":"item","numeric-id":260728,"id":"Q260728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1592813$43607E4A-976B-4FF4-A0BE-A97545A0DE2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"428714fc197079c690b239f5b46b25b66aadcbde","datavalue":{"value":{"entity-type":"item","numeric-id":1381543,"id":"Q1381543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1592813$F9413ADE-B47B-4763-A146-52ADC14DA113","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2e8211cf89fb3e58cebf657950368971306be793","datavalue":{"value":{"entity-type":"item","numeric-id":176881,"id":"Q176881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1592813$B2B1683F-37C1-4C1B-AD07-913131E0F296","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31707e7a13da914b31b6dd6f84fd3adca471dd41","datavalue":{"value":{"time":"+2002-06-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1592813$64FD8D8A-D552-4554-9D13-B935CB7A52C3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4fe1edcebd5811d3d8a71066100a841eb9d11a65","datavalue":{"value":"This paper investigates the asymptotic behaviour of the sequence \\(\\{f_n\\}\\) defined by means of a divide-and-conquer recursion  \\[  [2^n-(a_1+a_0)]f_n=a_1\\sum_{k=0}^{n-1}\\binom{n}{k}\\alpha^{n- k}f_k+b_1\\beta^n,\\quad n>l , \\tag{1}  \\]  where \\(\\alpha ,\\beta >0, a_0,a_1\\neq 0,b_1\\in\\mathbb R\\) are given parameters and \\(f_0,f_1,\\dots ,f_l\\) are the initial values. It is known that some particular cases of this recurrence relation admit a very different asymptotic behaviour of solutions. The main result of this paper gives a complete list of all possible types of the asymptotic behaviour of general recurrences defined by use of (1). The sign of \\(\\triangle =2\\alpha -\\beta\\) turns out to be the key assumption of this statement. Put \\(\\rho =\\log_2a_1\\). If \\(\\triangle >0\\), then  \\[  \\alpha^{-n}f_n=n^{\\rho}K(\\log _2n)+O(n^{\\rho -1}) , \\tag{2}  \\]  where \\(K\\) is an analytic and periodic function with period 1. If \\(\\triangle <0\\), then  \\[  \\left (\\frac{\\beta}{2}\\right)^{-n}f_n=b_1+O(n^{-1}) .  \\]  If \\(\\triangle =0\\), then some additional requirements on the value of \\(\\rho\\) are necessary to prove the modifications of formula (2). The method of the proof is based on considering the exponential generating function \\(f(z)\\) of the sequence \\(\\{f_n\\}\\) given by  \\[  f(z)=\\sum_{n=0}^{\\infty}\\frac{f_n}{n!}z^n .  \\]  It is shown that \\(f(z)\\) is an entire solution of the functional equation  \\[  f(2z)=(a_1\\text{ e}^{\\alpha z}+a_0)f(z)+b_1\\text{ e}^{\\beta z}+b_0(z)  \\]  and its asymptotic behaviour determines the asymptotics of \\(f_n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1592813$E04E0E8F-90A9-49BA-BE89-61DB54AA545E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"82f5b2338af7111d7fa2b3250da7166c5871caa4","datavalue":{"value":{"entity-type":"item","numeric-id":280022,"id":"Q280022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1592813$A680FBAA-C20F-4B47-8C8D-8A2EABA41757","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b00310b6d35f609c531eaeebde5582043cf50dcf","datavalue":{"value":"39A13","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1592813$862D7FD2-05B0-4FAB-A9A8-512BDA6ACFD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0711229aac3ca5692d90fe260ad34a34e2facc24","datavalue":{"value":"39A11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1592813$FA6BE807-1269-4023-899E-A15970669E43","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dba598d355ab6009220a5cd0f171995befd0d514","datavalue":{"value":"1556600","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1592813$A8541D1C-C589-4D58-B153-2A8FBE7DBB3E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fda179e832e730f1bfc59fb43fc52ab8afc83b27","datavalue":{"value":"divide-and-conquer recursion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1592813$5D795C17-7D5A-48E9-B1F2-F1B9B388D8B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8c9573404f466fc73de1e6d423407b5543ac068","datavalue":{"value":"asymptotic behaviour","type":"string"},"datatype":"string"},"type":"statement","id":"Q1592813$66950C09-FE5C-40BB-BB88-A0A4797121F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2a437b4112633cecfd0f705be393165ccc7ea1f","datavalue":{"value":"exponential generating function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1592813$6B880A91-0EAD-469D-AE9A-87D5D80259D7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1592813$018539AF-8357-485E-8BC6-2C96DC2FF4C6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d282bf46a3a96d5db5d45c961b6cf7f64f87d468","datavalue":{"value":"https://doi.org/10.1007/pl00000132","type":"string"},"datatype":"url"},"type":"statement","id":"Q1592813$9D5180B2-BF99-4CE0-A777-5FBB9738A1D4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3eef522d7f6f498b9010ebfed83ab069c9356eab","datavalue":{"value":"W1977753056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1592813$081DD5B2-3440-403E-AE6F-340CD32193AF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a9491c539b77db32a5c69dec32a716f77cedae2","datavalue":{"value":{"entity-type":"item","numeric-id":4554937,"id":"Q4554937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a877201f327742a1327aaace3690ac794b86b98","datavalue":{"value":{"amount":"+0.8708664178848267","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1592813$3015E475-4B28-434B-9507-EE43F41A8430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d1ff6ba208ffea158a150c6ae2ad398193e7cf0","datavalue":{"value":{"entity-type":"item","numeric-id":2920844,"id":"Q2920844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9ff3ea4355410dec0dbfe8d1f4a93dd6f6a5df5","datavalue":{"value":{"amount":"+0.8412718176841736","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1592813$21B21561-010F-46D8-9C52-C653AC302C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dfec2d1694ef849baa12bc42e43265c94e6dc81","datavalue":{"value":{"entity-type":"item","numeric-id":1401173,"id":"Q1401173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80fde08c53bf1c04fcb280f066362e07e8be7401","datavalue":{"value":{"amount":"+0.8140008449554443","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1592813$4BC3CE37-8098-4625-96BC-477DEB500A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93351d03d934e6a6e6b43cccc8128e0e5241fc18","datavalue":{"value":{"entity-type":"item","numeric-id":4630256,"id":"Q4630256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d356036e48eb9310ae8a508d828544df9cc2ddd","datavalue":{"value":{"amount":"+0.8087490200996399","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1592813$4F4B6723-3426-4D84-A5E4-D17FC914674E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c7a7ec86fabd291916ce404b0109464c6f00f96","datavalue":{"value":{"entity-type":"item","numeric-id":3034823,"id":"Q3034823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d34d1b011cacfe137194e86673a630098f07252f","datavalue":{"value":{"amount":"+0.8017718195915222","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1592813$00A0306A-520B-4678-955D-2B94B41B48E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Divide-and-conquer recurrences -- classification of asymptotics","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Divide-and-conquer_recurrences_--_classification_of_asymptotics"}}}}}