Przedstawić funkcję rekurencyjną w postaci jawnej

[czajna666]

Mam przedstawić funkcję rekurencyjną w postaci jawnej h(x), a nie mam pojęcia jak to zrobić. Czytałem coś na temat równań charakterystycznych ale nic mi to nie pomogło. Byłbym bardzo wdzięczny za wyjaśnienie na przykładzie tej funkcji sposobu postępowania przy takich zagadnieniach.

\(\displaystyle{ h(k) = 6h( \frac{k}{2}) + k ; k > 1}\)

\(\displaystyle{ h(1) = 1}\)

[Qń]

W postaci jawnej tego ciągu nie przedstawisz, bo nie jest on jednoznacznie określony (chyba, że tam jest część całkowita przy \(\displaystyle{ \frac k2}\)). Zapewne chodzi raczej o zbadanie jego rzędu wielkości. W tym celu możesz zacząć od podstawienia \(\displaystyle{ k=2^n}\), a następnie \(\displaystyle{ h(2^n)=g(n)}\) i wyznaczenia wzoru jawnego na \(\displaystyle{ g(n)}\).

Q.

[czajna666]

Jak to nie przedstawię tego w postaci jawnej, skoro tak jest w poleceniu? Raczej jest to część całkowita przy tym \(\displaystyle{ \frac{k}{2}}\) bo w poleceniu mam też sprawdzić wynik dla k = 8.

[abc666]

Podstaw tak jak mówi Qń
\(\displaystyle{ k=2^n}\)
możesz jeszcze dla uproszczenia podzielić stronami przez \(\displaystyle{ 6^{n}}\) i dokonać podstawienia

[czajna666]

\(\displaystyle{ g(n)= 6h(2 ^{n-1})+2 ^{n} /:6 ^{n}}\)
\(\displaystyle{ \frac{g(n)}{6 ^{n}} = h(2 ^{n-1}) * 6 ^{1-n}+ \frac{1}{3 ^{n} }}\)

I nie wiem co dalej z tym zrobić. Można prosić o dalsze wskazówki?

[abc666]

Źle podzieliłeś, powinno być
\(\displaystyle{ \frac{h(2 ^{n})}{6 ^{n}} = \frac{h(2 ^{n-1})}{6 ^{n-1}}+ \frac{1}{3 ^{n} }}\)
teraz podstaw \(\displaystyle{ g(n)=\frac{h(2 ^{n})}{6 ^{n}}}\), dostaniesz do obliczenia sumę ciągu geometrycznego

[czajna666]

Hmm, szczerze przyznam że się pogubiłem... Mogę prosić o wytłumaczenie całego tego przykładu krok po kroku żebym mógł go spokojnie przeanalizować. W internecie naprawdę ciężko znaleźć informacje na temat analogicznego przykładu.

[abc666]

\(\displaystyle{ h \left( k \right) = 6h \left( \frac{k}{2} \right) + k \qquad k > 1\\
h(1)=1}\)
Robimy podstawienie
\(\displaystyle{ k=2^n}\)
dostajemy
\(\displaystyle{ h\left( 2^{n}\right) =6h\left( \frac{2^{n}}{2}\right) +2^{n}\\
h\left( 2^{n}\right) =6h\left( 2^{n-1}\right) +2^{n}}\)
Jeśli podzielmy teraz stronami przez \(\displaystyle{ 6^{n}}\) dostaniemy
\(\displaystyle{ \frac{h\left( 2^{n}\right)}{6^{n}} =\frac{6h\left( 2^{n-1}\right)}{6^{n}} +\left( \frac{1}{3} \right) ^{n}\\
\frac{h\left( 2^{n}\right)}{6^{n}} =\frac{h\left( 2^{n-1}\right)}{6^{n-1}} +\left( \frac{1}{3} \right) ^{n}}\)
robimy teraz podstawienie
\(\displaystyle{ g(n)=\frac{h\left( 2^{n}\right)}{6^{n}}}\)
stąd
\(\displaystyle{ g(n)=g(n-1)+\left( \frac{1}{3} \right) ^{n}}\)
Teraz rozpisujemy prawą stronę aż zejdziemy do \(\displaystyle{ g(0)}\)
\(\displaystyle{ g(n)=g(n-1)+\left( \frac{1}{3} \right) ^{n}=\underbrace{g(n-2)+\left( \frac{1}{3} \right) ^{n-1}}_{g(n-1)}+\left( \frac{1}{3} \right) ^{n}=...\\
=g(0)+\frac{1}{3}+\left( \frac{1}{3} \right) ^{2}+...+\left( \frac{1}{3} \right) ^{n}}\)
\(\displaystyle{ g(0)=\frac{h\left( 2^{0}\right)}{6^{0}}=h(1)=1}\)
Czyli
\(\displaystyle{ g(n)=1+\frac{1}{3}+...+\left( \frac{1}{3} \right) ^{n}}\)
Jest to zwykła suma ciągu geometrycznego, stosujemy wzór
\(\displaystyle{ g(n)=\frac{3}{2}- \frac{1}{2}\cdot \left( \frac{1}{3} \right) ^{n}}\)

Wracamy do podstawienia
\(\displaystyle{ \frac{h\left( 2^{n}\right)}{6^{n}}=\frac{3}{2}- \frac{1}{2}\cdot \left( \frac{1}{3} \right) ^{n}\qquad |\cdot 6^{n} \\
h\left( 2^{n}\right)=6^{n}\cdot \frac{3}{2} - \frac{1}{2}\cdot 2 ^{n}}\)
teraz mamy
\(\displaystyle{ n=\log_{2}k}\)

\(\displaystyle{ h(k)= \frac{3}{2}\cdot 6^{\log_{2}k}-\frac{1}{2}k\qquad k>1}\)

Oczywiście ten wzór jest słuszny tylko dla \(\displaystyle{ k=2^m}\), gdzie \(\displaystyle{ m\in \mathbb{N}}\)
Spróbuj sam przeanalizować co trzeba by tu zmień jeśli za radą Qń-a dodamy tam tą część całkowitą.

[czajna666]

Dziękuję bardzo. Jednego tylko nie rozumiem:

Jest to zwykła suma ciągu geometrycznego, stosujemy wzór
\(\displaystyle{ g(n)=\frac{3}{2}- \frac{1}{2}\cdot \left( \frac{1}{3} \right) ^{n}}\)

W tym miejscu skorzystałeś z wzoru na sumę ciągu geometrycznego? ( \(\displaystyle{ a_{1}* \left( \frac{1- q^{n} }{1-q} \right)}\) )
Nie powinno być:
\(\displaystyle{ g(n)=\frac{3}{2}- \frac{3}{2}\cdot \left( \frac{1}{3} \right) ^{n}}\)
?

[abc666]

Zauważ, że jest \(\displaystyle{ n+1}\) wyrazów w ciągu więc mamy
\(\displaystyle{ g(n)=\frac{3}{2}- \frac{3}{2}\cdot \left( \frac{1}{3} \right) ^{n+1}=\frac{3}{2}- \frac{1}{2}\cdot \left( \frac{1}{3} \right) ^{n}}\)

[czajna666]

Dziękuje bardzo za pomoc:) Teraz zaliczenie algorytmów wydaję się o wiele prostsze:)