Here is my attempt at lower bounding the number of SAWs on $\mathbb{Z}^d$ of length $n$: In $\mathbb{Z}^d$, consider the $2^{d-1}$ lines of the form $\epsilon_1 x_1 = \epsilon_2 x_2 = \epsilon_3 x_3 \dots \epsilon_d x_d$ where each $\epsilon_i \in \{ -1, 1\}$(specially $\epsilon_1 = 1$) and $X_1, X_2 \dots X_d$ are axes of $\mathbb{Z}^d$. We notice that given a point $w = (w_1, w_2 \dots w_d) \in \mathbb{Z}^d$, we have that the projection of $w$ onto $\epsilon_1 x_1 = \epsilon_2 x_2 = \epsilon_3 x_3 \dots \epsilon_d x_d$ is given by the point $$ w_0 = \left ( \epsilon_1 \cdot\frac{\sum\limits_{j=1}^d \epsilon_j w_j}{d}, \epsilon_2 \cdot\frac{\sum\limits_{j=1}^d \epsilon_j w_j}{d}, \dots ,\epsilon_d \cdot\frac{\sum\limits_{j=1}^d \epsilon_j w_j}{d} \right )$$ Notice that when you are performing a SAW on $\mathbb{Z}^d$, you are incrementing exactly one of the $d$-coordinates by $\pm 1$, so each co-ordinate of $w_0$ either increments or decrements by a fixed value. This means that we can interpret each projection of $w$ onto one of the $2^{d-1}$ lines as a random walk on $\mathbb{Z}$ with incrementing length a fixed non-zero real number. Moreover, during an SAW on $\mathbb{Z}^d$, each of the random walks increment in either direction and given any configuration of the $2^{d-1}$ many random walks, we can associate a unique position in $\mathbb{Z}^d$.
Now that we have this interpretation, we express a SAW on $\mathbb{Z}^d$ as a tuple of random walks $(\mathcal{S}_1, \mathcal{S}_2, \dots, \mathcal{S}_{2^{d-1}})$ on the $2^{d-1}$ many lines. To simulate a SAW out of these random walks, we choose $k$ of these random walks and choose a direction (negative or positive according to the convention chosen on each such line) and exclusively move each of those random walks in those $k$ directions, $k$ running from $1$ to $2^{d-1}$. The rest of the $2^{d-1}-k$ random walks can be performed arbitrarily. This simulation will generate an SAW, as you can revisit a point only when each of the $2^{d-1}$ random walks will visit the same point simultaneously, but that never happens as we increment the $k$ chosen random walks in a fixed direction each turn. Hence, it never visits the same point ever again. The number of ways of simulating such random walks is given by (according to me, using inclusion-exclusion) $$\sum\limits_{k=1}^{2^{d-1}} (-1)^{k+1} \cdot 2^k \cdot \dbinom{2^{d-1}}{{k}} \cdot \left (2^{2^{d-1}-k}\right )^n$$ where the $2^k$ comes from choosing the directions of incrementation of the $k$ chosen random walks, $\dbinom{2^{d-1}}{{k}}$ is the number of ways of choosing these $k$ random walks out of a total of $2^{d-1}$ many random walks, and $2^{d-1}-k$ is the number of remaining random walks, and $\left(2^{2^{d-1}-k}\right )^n$ is simply choosing a random direction for the $2^{d-1}-k$ many random walks, and doing this for $n$ length walks. We observe that the inclusion exclusion part takes care of the overcounting.
But the PROBLEM here is that this number exceeds $2d(2d-1)^{n-1}$ for large $n, d$ which is the upper bound for the number of SAWs on $\mathbb{Z}^d$ of length $n$, but this expression should be a lower bound ideally. That means there is an error in my reasoning. Can you please point out the error in my calculations? I appreciate your help.
