Use induction

$a_{2k}=a_k+a_{2k-1}=a_k+a_{2k-2}=a_k+a_{k-1}+a_{2k-3}=...=a_k+a_{k-1}+...+a_1+1$ $a_{2^n}=a_{2^{n-1}}+...+a_1+1=a_{2^{n-1}}+...+a_{2^{n-2}+1}+a_{2^{n-1}}<(2^{n-2}+1)a_{2^{n-1}}<2^{n-1}a_{2^{n-1}}$ So $a_{2^n}<2^{n-1}2^{n-2}....2a_1=2^{\frac{n^2-n}{2}}$ Please check

RagvaloD wrote: $a_{2k}=a_k+a_{2k-1}=a_k+a_{2k-2}=a_k+a_{k-1}+a_{2k-3}=...=a_k+a_{k-1}+...+a_1+1$ $a_{2^n}=a_{2^{n-1}}+...+a_1+1=a_{2^{n-1}}+...+a_{2^{n-2}+1}+a_{2^{n-1}}<(2^{n-2}+1)a_{2^{n-1}}<2^{n-1}a_{2^{n-1}}$ So $a_{2^n}<2^{n-1}2^{n-2}....2a_1=2^{\frac{n^2-n}{2}}$ Please check It's absolutely same to my solution