rekurencja C: Jak rozwiązać rekurencję daną wzorem a_n+1−a_n=2ⁿ−2n−1 a₀=1 ? Bo rozwiązywanie tego "zwykłym " sposobem nie daje mi wyniku. Według wolframa rozwiązaniem jest 2ⁿ−n²

Mariusz: Równanie wygląda jak po zastosowaniu czynnika sumacyjnego więc wystarczy zsumować część niejednorodną ale polecam do takich równań funkcję tworzącą

jc: a_n = 1 + 1 + 2 + 2² + ... + 2ⁿ⁻¹ − 1 − 3 − 5 − ... − (2n−1) = 2ⁿ − n² bo 1 + 1 + 2 + 2² + ... + 2ⁿ⁻¹ = 2ⁿ oraz 1 + 3 + 5 + (2n−1) = n²

C: A mógłby mi ktoś rozpisać jak rozwiązać to funkcją tworzącą?

C: ?

Mariusz:

	1
an=an−1+		2n−2(n−1)−1
	2

	1
an=an−1+		2n−2n+1
	2

A(x)=∑_n=0^∞a_nxⁿ

	1
∑n=1∞an=∑n=1∞an−1xn+∑n=1∞		2nxn−∑n=1∞2nxn+
	2

∑_n=1^∞xⁿ

	1	2x		x
∑n=1∞an=x∑n=1∞an−1xn−1+			−∑n=1∞2nxn+
	2	1−2x		1−x

	1
∑n=0∞xn=
	1−x

d		d		1
	(∑n=0∞xn)=		(		)
dx		dx		1−x

	1
∑n=0∞nxn−1=−		(−1)
	(1−x)2

	1
∑n=1∞nxn−1=
	(1−x)2

	x
∑n=1∞nxn=
	(1−x)2

	x		2x		x
∑n=1∞an=x∑n=1∞an−1xn−1+		−		+
	1−2x		(1−x)2		1−x

	x		−x2−x
∑n=0∞an−1=x∑n=0∞anxn+		+
	1−2x		(1−x)2

	x		−3x+1
A(x)(1−x)=		+
	1−2x		(1−x)2

	x		−3x+3−2
A(x)=		+
	(1−2x)(1−x)		(1−x)3

	1−x)−(1−2x)		3		2
A(x)=		+		−
	(1−2x)(1−x)		(1−x)2		(1−x)3

	1		1		3		2
A(x)=		−		+		−
	1−2x		1−x		(1−x)2		(1−x)3

	x
∑n=0∞(n+1)xn+1=
	(1−x)2

	1
∑n=0∞(n+1)xn=
	(1−x)2

d		d		1
	(∑n=0∞(n+1)xn)=		(		)
dx		dx		(1−x)2

	2
∑n=0∞n(n+1)xn−1=−		(−1)
	(1−x)3

	2
∑n=1∞n(n+1)xn−1=
	(1−x)3

	2
∑n=0∞(n+1)(n+2)xn=
	(1−x)3

A(x)=∑_n=0^∞2ⁿxⁿ−∑xⁿ+3∑(n+1)x²−∑_n=0^∞(n+1)(n+2)x² a_n=2ⁿ−1+3(n+1)−(n+1)(n+2) a_n=2ⁿ−1+3n+3−n²−3n−2 a_n=2ⁿ−n²